sorting a linked list

This is a discussion on sorting a linked list within the C Programming forums, part of the General Programming Boards category; What is the proper way to sort a linked list. This was all I could think up. Code: int change ...

  1. #1
    Registered User
    Join Date
    Apr 2008
    Posts
    32

    sorting a linked list

    What is the proper way to sort a linked list. This was all I could think up.

    Code:
            
            int change = 1;
            while ( change )
            {
                    change = 0;
                    current = start;
                    next = current->next;
                    do
                    {
                            if ( current->data > next->data)
                            {
                                    swapping code goes here;;;
                                   change=1;
                            }
                            current = current->next;
                            next = current->next;
                    } while ( current->next );
            }

  2. #2
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    And what would you think that you should do?

    I can think of two solutions:
    Swap places within the linked list (you need to know the previous link for that, so that you can update the next pointer of the previous node)
    Swap the actual data.

    Sorting linked lists is often best done by creating a new list by insertion sorting the new list.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  3. #3
    Registered User
    Join Date
    Apr 2008
    Posts
    32
    This is what I have for the swap code.

    Code:
      int change = 1; 
      char word[80];
      while ( change )
            {
                    change = 0;
                    current = start;
                    next = current->next;
                    do
                    {
                            if ( strcmp(current->word, next->word) > 0 )
                            {
                                    strcpy(word, current->word);
                                    strcpy(current->word,  next->word);
                                    strcpy(next->word, word);
                                    change=1;
                            }
                            current = current->next;
                            next = current->next;
    
                    } while ( current->next );
            }

  4. #4
    Registered User
    Join Date
    Apr 2008
    Posts
    32
    I just have never done this before. Linked list are still new to me. So if it works. it is correct :-)

  5. #5
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Seeing as you have (potentially) rather long strings, you may want to recreate the list instead by removing the element from the original list, and placing it in a new fresh list [at the right place, of course].

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. single linked list to double linked list (help)
    By Countfog in forum C Programming
    Replies: 8
    Last Post: 04-29-2008, 08:04 PM
  2. singly linked to doubly linked
    By jsbeckton in forum C Programming
    Replies: 10
    Last Post: 11-06-2005, 06:47 PM
  3. Please Help - Problem with Compilers
    By toonlover in forum C++ Programming
    Replies: 5
    Last Post: 07-23-2005, 10:03 AM
  4. Linked list with two class types within template.
    By SilasP in forum C++ Programming
    Replies: 3
    Last Post: 02-09-2002, 05:13 AM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM

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