Name Sorting

This is a discussion on Name Sorting within the C Programming forums, part of the General Programming Boards category; Hi, I have created a program to sort names... I have used insertion sort here.. and i swap pointers instead ...

  1. #1
    Its not rocket science vasanth's Avatar
    Join Date
    Jan 2002
    Posts
    1,683

    Name Sorting

    Hi,
    I have created a program to sort names... I have used insertion sort here.. and i swap pointers instead of the strings themselves... The program accepts the names through the command line argument.. The program workks but please go through and comment and recomend improvements and i have a feeling i have not handled pointers properly.. it would be grat if you could point them out...

    the code is

    Code:
    # include <stdio.h>
    # include <stdlib.h>
    void insertion (char **a, int n);
    
    int
    main (int argc, char *argv[])
    {
      int i;
    
      char **namelist = (char **) calloc (argc - 1, sizeof (char *));
    
      if (namelist == NULL)
        {
          printf ("\nError allocating memory");
          exit (1);
        }
    
    
    
    
      for (i = 0; i < argc - 1; i++)
        {
          namelist[i] = (char *) calloc (sizeof (argv[i]), sizeof (char));
          strcpy (namelist[i], argv[i + 1]);
        }
    
      insertion (namelist, argc - 1);
    
      for (i = 0; i < argc - 1; i++)
        printf ("%s\n", namelist[i]);
    
    
    
      for (i = 0; i < argc - 1; i++)
        free (namelist[i]);
    
      free (namelist);
    
    
      return 0;
    }
    
    
    void
    insertion (char **a, int n)
    {
    
      int i, j;
      char *v;
      for (i = 1; i < n; i++)
        {
    
          v = a[i];
    
          j = i;
    
          while (strcmp (a[j - 1], v) == 1)
    	{
    	  a[j] = a[j - 1];
    	  j = j - 1;
    	  if (j <= 0)
    	    break;
    
    	}
    
          a[j] = v;
        }
    }
    thanx
    bye

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,823
    > namelist[i] = (char *) calloc (sizeof (argv[i]), sizeof (char));
    Man, 1200+ posts and you're still mixing sizeof() with strlen()

    There's a minor gotcha with using strlen(), so I'm going to see if you can avoid falling into that hole as well.

    And you're ignoring the previous suggestions / FAQ entries on not casting malloc.

    You're not still using some fossil DOS compiler are you? Because it's only DOS which would tolerate such blatant abuse of memory.


    > while (strcmp (a[j - 1], v) == 1)
    GO READ THE MANUAL PAGE
    Code:
    DESCRIPTION
           The  strcmp()  function compares the two strings s1 and s2.  It returns
           an integer less than, equal to, or greater than zero if  s1  is  found,
           respectively, to be less than, to match, or be greater than s2.
    It's > 0 you want, not == 1

    And please include all the correct header files for the functions you use.

    > char **namelist = (char **) calloc (argc - 1, sizeof (char *));
    I bet you don't know that argc can be zero

    > The program workks but please go through and comment
    Heh - the sloppy memory allocation and the broken strcmp() call suggests you had some very limited tests.

    This is all basic stuff, nevermind the actual implementation of the algorithm in question.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  3. #3
    Its not rocket science vasanth's Avatar
    Join Date
    Jan 2002
    Posts
    1,683
    thanks.. i will go through them and correct them..... i have actually never used malloc but used the new operator(in C++)..I am using gcc but no idea why its not warning me.
    Last edited by vasanth; 11-09-2003 at 04:14 AM.

  4. #4
    Its not rocket science vasanth's Avatar
    Join Date
    Jan 2002
    Posts
    1,683
    Hi again,
    I have modified my code.. can you please review it now and give me suggestions


    Code:
    # include <stdio.h>
    # include <stdlib.h>
    # include <string.h>
    
    # define MAXLENGTH 20		/*maxlength defined for array to accept names */
    
    void insertion (char *a[], int n);
    
    int
    main (void)
    {
      int num, i;
      char name[MAXLENGTH];
      char **namelist;
    
      printf ("\nEnter the number of names you want to enter >");
      scanf ("%d", &num);
    
      /*An array of pointers is created dynamically and checked for allocation errors */
      if ((namelist =  calloc (num, sizeof (char *))) == NULL)
        {
          printf ("\nError allocating memory");
          exit (1);
        }
    
    
      /*
         The loop is run num number of times and names are accepted 
         into the fixed length array name. And memory is dynamically allocated for the length of name
         and the contents are transfered
       */
      for (i = 0; i < num; i++)
        {
          printf ("Enter name %d>", i + 1);
          scanf ("%19s", name);
    
          if ((*(namelist + i) =calloc (strlen (name), sizeof (char))) == NULL)
    	{
    	  printf ("\nError allocating memory");
    	  for (i--; i >= 0; i--)	/* If an error occurs allocating memory the previous allocations are aslo deallocated and the program quits */
    	    free (*(namelist + i));
    
    	  free (namelist);
    	  exit (1);
    	}
          else
    	strcpy (*(namelist + i), name);	/*The name is transfered to the newly allocated space */
    
    
        }
    
      insertion (namelist, num);	/*The sort function is called */
    
    
      printf ("\nSORTED ARRAY:\n");
    
    /*
    The sorted array is printed and after each print the specific space is deallocated
    */
      for (i = 0; i < num; i++)
        {
          printf ("\n %s", *(namelist + i));
          free (*(namelist + i));
        }
    
      free (namelist);
      printf ("\n");
      return 0;
    }
    
    
    void
    insertion (char *a[], int n)
    {
      int i, num;
      char *temphold;		/*Temporary Variable to hold a pointer address when swaping pointers */
    
      for (i = 1; i < n; i++)	/*Loop is run n number of times which is the number of elements */
        {
          num = i;			/*The value of i is copied into num for manipulation in the while loop */
    
    
          /*
             The while loop is run until all the elements in the left section of the array are sorted
           */
          while (strcmp (*(a + num), *(a + num - 1)) < 0)
    	{
    	  temphold = *(a + num);	/*Swapping part */
    	  *(a + num) = *(a + num - 1);
    	  *(a + num - 1) = temphold;
    
    	  if (num - 1 == 0)	/*(While) loop terminated on reaching 1st element of the array */
    	    break;
    	  else
    	    num--;		/*Num is decremented to compare previous elements inside a given section */
    	}
        }
    
    
      return;
    }
    thanx in advance
    bye

  5. #5
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,823
    > *(namelist + i)
    So why did you change this from the more readable namelist[i]?

    > calloc (strlen (name), sizeof (char))
    LOL - I told you about this trap in advance, and you still fell into it.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  6. #6
    Its not rocket science vasanth's Avatar
    Join Date
    Jan 2002
    Posts
    1,683
    Originally posted by Salem
    > *(namelist + i)
    So why did you change this from the more readable namelist[i]?

    > calloc (strlen (name), sizeof (char))
    LOL - I told you about this trap in advance, and you still fell into it.
    hmmm i thought that the pointer notation is faster than the subscript notation.. anyways..

    could you please explain to me what the trap is..


    thanx in advance

  7. #7
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,823
    > could you please explain to me what the trap is..
    The fact that you should malloc strlen(name)+1 bytes if you ever hope to store the \0 at the end of the string successfully.

    > hmmm i thought that the pointer notation is faster than the subscript notation
    Perhaps you should look at the assembler output and compare.

    Perhaps you should understand that [] is just a syntactic variation (which I think is easier to read) and that the compiler treats them both as the same thing.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  8. #8
    Its not rocket science vasanth's Avatar
    Join Date
    Jan 2002
    Posts
    1,683
    ok i analysed what was happening.. if i am right i have to put

    Code:
    > calloc (strlen (name)+1, sizeof (char))
    since space needs to be also allocated for the string terminating char... am i right

  9. #9
    Its not rocket science vasanth's Avatar
    Join Date
    Jan 2002
    Posts
    1,683
    Originally posted by vasanth
    ok i analysed what was happening.. if i am right i have to put

    Code:
    > calloc (strlen (name)+1, sizeof (char))
    since space needs to be also allocated for the string terminating char... am i right
    edit
    -----



    You beat me to it... Thanks .. do you think my deallocation of memory is being done right..

  10. #10
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,823
    Your deallocation looks good
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Sorting algorithms, worst-case input
    By Leftos in forum C++ Programming
    Replies: 17
    Last Post: 06-15-2009, 02:33 PM
  2. Need help with linked list sorting function
    By Jaggid1x in forum C Programming
    Replies: 6
    Last Post: 06-02-2009, 03:14 AM
  3. sorting structure members using pointers
    By robstr12 in forum C Programming
    Replies: 5
    Last Post: 07-25-2005, 06:50 PM
  4. Still Needing Help : selection sorting
    By Unregistered in forum C Programming
    Replies: 6
    Last Post: 10-14-2001, 09:41 PM
  5. selection sorting
    By Unregistered in forum C Programming
    Replies: 5
    Last Post: 10-13-2001, 09:05 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21