Thread: help with sorting a list :(

  1. #1
    Learner Axel's Avatar
    Join Date
    Aug 2005
    Posts
    335

    help with sorting a list :(

    I'm stuck on this problem. I've been trying for days figuring out how to fix it. I have a linklist.. I want to sort it alphabetically, i'm almost there but the functionnn has a few bugs:

    The output for the following code:

    Androd
    Dog
    Bat


    as you can see... the last element comes before alphabetically before the previous one my sort method does not handle it. Does anyone know how to fix this? (the code in bold indicates where the problem is)

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    struct charNode
    {
       char petName[12];
    
       struct charNode *next;
    };
    
    typedef struct charNode charNode;
    
    void addElement(charNode **start, char *petName);
    void printList(charNode *start);
    charNode* newNode(char *petName);
    void getString(charNode *start);
    charNode *sort(charNode *start);
    charNode *reverse(charNode *head);
    
    int main()
    {
       charNode *start = NULL;
    
       getString(start);
      
       return 0;
    }
    
    
    void getString(charNode *start)
    {
    
    
       addElement(&start, "Dog");
         addElement(&start, "Androd");
         addElement(&start, "Bat");  
    
         start = sort(start);
         printf("\n");
         printf("\n");
           printList(start);
    
    }
    
    void addElement(charNode **start, char *petName)
    {
    
       charNode *temp,*prev, *loc;
       int i;
    
       temp = newNode(petName);
    
    
       if (*start == NULL)
       {
          *start = temp;
       }
    
       else
       {
          loc = *start;
          prev = NULL;
    
           for (i=0; loc != NULL; i++)
           {
       
               	prev = loc;
    			loc = loc->next;
            }
    	      if (prev == NULL)
             {     
                *start = temp;
             }
             else
             {
                prev->next = temp;  
             }
       }
      
    
    }
    
    charNode* newNode(char *petName)
    {
    
       charNode *temp;
    
       temp = (charNode *) malloc(sizeof(charNode));
       if (temp == NULL)
       {
          printf("WARNING - Memory allocation error\n");
          exit(EXIT_FAILURE);
       }
    
    
      strcpy(temp->petName, petName);
    
    
       temp->next = NULL;
    
       return temp;
    }
    
    
    void printList(charNode *start)
    {
    
       while (start != NULL)
       {
    
          printf("%s\n", start->petName);
          start = start->next;
       }
    }
    charNode *sort(charNode *start)
    {
    
       charNode *temp = NULL;
       charNode *prev = NULL;
       charNode *current = start;
    
       if (start!=NULL)
       {
          if (start->next != NULL)
          {
             prev = start;
             current = start;
    
             while (current != NULL)
             {
                if ( strcmp(current->petName, start->petName) <0)
                {
                   prev->next = current->next;     
                   temp = start;      
                   start = current;      
                                         
                   start->next = temp;   
                }
             
                else
                   prev = current;
                   current = current->next;
             }
          }
       }
       return start;
    }

  2. #2
    The C eater *munch*
    Join Date
    Oct 2006
    Posts
    101
    Code:
          if (start->next != NULL)
          {
             prev = start; 
             current = start; //  assigning current to start 
    
             while (current != NULL) // so current == start rite? 
             { 
                if ( strcmp(current->petName, start->petName) <0) // checking the same thing? no?
    and another hint :
    strcmp returns 0 , < 0 and > 0 if the strings are same, less than or greater than respectively

  3. #3
    Learner Axel's Avatar
    Join Date
    Aug 2005
    Posts
    335
    yes in the first iteration the first element is compared to it self but as the loop progresses this isnt the case.

  4. #4
    The C eater *munch*
    Join Date
    Oct 2006
    Posts
    101
    your code is pretty inefficient and unneccesarily long... but anw, the problem you are having was that you sort the list once only

    so if you have something like
    Code:
    "z" -> "d" -> "x" -> "c" -> NULL
    it will get to
    Code:
    "d" -> "x" -> "c" -> "z" -> NULL
    and your sort will quit

    and your strcmp check is still insufficient

    try this
    Code:
    #include <string.h>
    #include <stdio.h>
    
    int main() {
       printf("%d\n", strcmp("aab", "aac"));
       printf("%d\n", strcmp("aab", "aaa"));
       return 0;
    }
    Last edited by yxunomei; 10-15-2006 at 06:41 AM.

  5. #5
    Fear the Reaper...
    Join Date
    Aug 2005
    Location
    Toronto, Ontario, Canada
    Posts
    625
    It appears to me as though you're always swapping start when you'd really want to be swapping prev. Even at that, though your loop is missing comparisons. If I were you, I'd make another function, swap(a,b), that swaps 2 elements of your linked-list, that way in your sort you won't have to worry too much about all that pointer logic.
    Teacher: "You connect with Internet Explorer, but what is your browser? You know, Yahoo, Webcrawler...?" It's great to see the educational system moving in the right direction

  6. #6
    Learner Axel's Avatar
    Join Date
    Aug 2005
    Posts
    335
    Quote Originally Posted by yxunomei
    your code is pretty inefficient and unneccesarily long... but anw, the problem you are having was that you sort the list once only

    so if you have something like
    Code:
    "z" -> "d" -> "x" -> "c" -> NULL
    it will get to
    Code:
    "d" -> "x" -> "c" -> "z" -> NULL
    and your sort will quit
    yes exactly.... but if i run the same sort again and it doesn't change it. For example after "swap" runs we get:

    Androd
    Dog
    Bat


    if we run swap again

    we get:

    Code:
     if ( strcmp(current->petName, start->petName) <0)
    Androd < Androd == false


    Code:
     if ( strcmp(current->petName, start->petName) <0)
    Dog < Androd == false

    Code:
     if ( strcmp(current->petName, start->petName) <0)
    Bat < Androd == false


    ...so nothing changes :| any ideas on how to make it more efficient ?

  7. #7
    The C eater *munch*
    Join Date
    Oct 2006
    Posts
    101
    what was your original input?
    Last edited by yxunomei; 10-15-2006 at 06:52 AM.

  8. #8
    Learner Axel's Avatar
    Join Date
    Aug 2005
    Posts
    335
    Quote Originally Posted by Happy_Reaper
    It appears to me as though you're always swapping start when you'd really want to be swapping prev. Even at that, though your loop is missing comparisons. If I were you, I'd make another function, swap(a,b), that swaps 2 elements of your linked-list, that way in your sort you won't have to worry too much about all that pointer logic.

    Actually i've thought about (comparing prev with current and swap) this but then that still wouldn't work cause it won't for certain sort the list:


    unsorted list:

    A C D Z B


    ACDBZ

    so it isn't really sorted :/

  9. #9
    Fear the Reaper...
    Join Date
    Aug 2005
    Location
    Toronto, Ontario, Canada
    Posts
    625
    yes, but that's because you're updating things too quickly and missing comparisons. You should only update prev to prev-> next in what I'm showing you. Then, when if prev == current, then reset prev to start and current to current-> next. That should cover all the comparisons, in which case, as long as you're swapping right, will sort your list.
    Teacher: "You connect with Internet Explorer, but what is your browser? You know, Yahoo, Webcrawler...?" It's great to see the educational system moving in the right direction

  10. #10
    Learner Axel's Avatar
    Join Date
    Aug 2005
    Posts
    335
    Quote Originally Posted by Happy_Reaper
    yes, but that's because you're updating things too quickly and missing comparisons. You should only update prev to prev-> next in what I'm showing you. Then, when if prev == current, then reset prev to start and current to current-> next. That should cover all the comparisons, in which case, as long as you're swapping right, will sort your list.
    ok i've did what you suggested (i.e. swap prev rather than start ) but i get an endless loop :|

    Code:
    charNode *sort(charNode *start)
    {
    
       charNode *temp = NULL;
       charNode *prev = NULL;
       charNode *current = start;
    
       if (start!=NULL)
       {
          if (start->next != NULL)
          {
             prev = start;
             current = start;
    
             while (current != NULL)
             {
                if ( strcmp(current->petName, prev->petName) <0)
                {
                   prev->next = current->next;     
                   temp = prev;      
                   prev = current;      
                                         
                   start->next = temp;   
                }
             
                else
                   prev = current;
                   current = current->next;
             }
          }
       }
       return start;
    }
    what was your original input?
    Dog
    Androd
    Bat

  11. #11
    Learner Axel's Avatar
    Join Date
    Aug 2005
    Posts
    335
    If i can get the above to work i guess the solution for sorting and the guarantee that it will be sorted will be to run the sort method X number of times the linked list size is so if the linked list is 5 if i run the sort method 5 times and it swaps each adjacent element (if its out of place) then it should work...

  12. #12
    The C eater *munch*
    Join Date
    Oct 2006
    Posts
    101
    Code:
    "z" -> "x" -> "y" -> "d" -> "e" -> NULL
     ^      ^
    prev  next        // compare and swap when required (1)
    
    "x" -> "z" -> "y" ... -> NULL
            ^      ^
              prev  next // same as above (2)
    
    etc
    5 times yes...
    and on this part
    Code:
    while (current != NULL)
             {
                if ( strcmp(current->petName, prev->petName) <0)
                {
                   prev->next = current->next;     
                   temp = prev;      
                   prev = current;      
                                         
                   start->next = temp;   
                }
             
                else
                   prev = current;
                   current = current->next;
             }
    you see, if the strings are different, it will be swapped accordingly, and on the next iteration, current will be the same as prev rite? therefore on the next iteration, you will be comparing yet the same thing again... so according to you, you will need 2 * linked list size = 10 in your case rite?

    that's inefficient?

    yes exactly.... but if i run the same sort again and it doesn't change it. For example after "swap" runs we get:

    Androd
    Dog
    Bat
    well, if that doesn't work, then tell me how you can make
    Dog
    Androd
    Bat
    to

    Androd
    Dog
    Bat
    Last edited by yxunomei; 10-15-2006 at 08:00 AM.

  13. #13
    Learner Axel's Avatar
    Join Date
    Aug 2005
    Posts
    335
    Quote Originally Posted by yxunomei
    Code:
    "z" -> "x" -> "y" -> "d" -> "e" -> NULL
     ^      ^
    prev  next        // compare and swap when required (1)
    
    "x" -> "z" -> "y" ... -> NULL
            ^      ^
              prev  next // same as above (2)
    
    etc
    iteration, current will be the same as prev rite? therefore on the next iteration, you will be comparing yet the same thing again...
    i have tried adding:

    Code:
                                current = current->next;
    after this line:
    Code:
                  prev = current;
    but the endless loop is still there ? whats the problem

  14. #14
    The C eater *munch*
    Join Date
    Oct 2006
    Posts
    101
    im getting confused by ur code ... T_T ...

    tell me how you want those to be working and also what's actually happening in your code

    i'll give you a bit of help with codes
    Code:
    charNode *sort(charNode *start)
    {
    
       charNode *temp = NULL;
       charNode *prev = NULL;
       charNode *current = NULL;
       charNode *currentIn = NULL;
    
       // if the list was empty or has only one item on it, we bother not doing anything
       if(start == NULL || start->next == NULL) { 
          return start;
       }
       
       prev = start; // to keep track on the item before current
      
       // use for loop, easier to understand in this case
       for( current = start->next; current != NULL; current = current->next ) {
          
          // we need the nested loop to swap the list multiple times (in this case 5 times)
          for( currentIn = start->next; currentIn != NULL; current = currentIn->next) { 
             // do the swapping here;
          }
       }
    Last edited by yxunomei; 10-15-2006 at 08:40 AM.

  15. #15
    Learner Axel's Avatar
    Join Date
    Aug 2005
    Posts
    335
    Ok we have the following items in the list:

    Dog
    Androd
    Bat

    this is only for the first iteration...

    Code:
    while (current != NULL) // keep looping till the end....
             {
                if ( strcmp(current->petName, prev->petName) <0)  /* IF Androd is smaller than Dog == TRUE */
                {
                   prev->next = current->next;     /* this is just saying  Androd = Androd  */
                   temp = prev;     /* place "prev" i.e.  Dog in a temporary variable */
                   prev = current;      /* place current (Androd) to prev (Dog) so we have Androd, Dog
                                         
                }
             
                else
                   prev = current; // keep track of the previous item
                   current = current->next; // move current after prev
             }
    edit: actually the result is the following:

    Dog
    Bat

    dunno what the hell went wrong :|

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Following CTools
    By EstateMatt in forum C Programming
    Replies: 5
    Last Post: 06-26-2008, 10:10 AM
  2. Replies: 3
    Last Post: 03-04-2005, 02:46 PM
  3. Replies: 6
    Last Post: 03-02-2005, 02:45 AM
  4. compiler build error
    By KristTlove in forum C++ Programming
    Replies: 2
    Last Post: 11-30-2003, 10:16 AM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM