Thread: Sorting a linked list

  1. #1
    Registered User
    Join Date
    Oct 2010
    Posts
    4

    Sorting a linked list

    Hello!
    I've been trying to figure out a way to sort a linked list, but I allways face problems.
    my linked list is basicaly simpe:
    Code:
    typedef struct{
                   int value;
                   Node *next;
    };
    After filling the lnked list with 100 nodes, I need to sort it based on value and. What I was thinking is that I could search for the max value and put the node found on the begining of a new list; However, this didn't work. I wonder if anybody here would explain to me a better way to do the sorting. Thanks!

  2. #2
    Registered User
    Join Date
    Jan 2010
    Posts
    34
    you must implement a recursive sorting.
    Starting from the first node, if the i node value is bigger than the i+1 one, you change the next assignement, and so on.

  3. #3
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    >After filling the lnked list with 100 nodes
    It's often better to keep the list sorted at all times rather than have a separate sorting step:
    Code:
    int add_sorted(struct node **list, int data)
    {
        struct node *p = malloc(sizeof *p);
    
        if (p == NULL)
            return 0;
    
        p->data = data;
        p->next = NULL;
    
        if (*list == NULL || data < (*list)->data) {
            p->next = *list;
            *list = p;
        }
        else {
            struct node *it = *list;
    
            while (it->next != NULL)
                it = it->next;
    
            it->next = p;
        }
    
        return 1;
    }
    >What I was thinking is that I could search for the max value and put the node found on the begining of a new list
    That's the right idea for a selection sort. If it didn't work, you probably have issues with pointer surgery between two linked lists. Post your attempt and someone will be able to explain where it goes wrong.
    My best code is written with the delete key.

  4. #4
    Registered User
    Join Date
    Aug 2010
    Posts
    231
    you can also working iterativ (far less stack problems) if you use a help-array and qsort, eg:

    if size is your ll-size and root points to the first element:

    Code:
    int size = ???, i;
    Node *root = ???, *p;
    void **a;
    
        puts("Unsorted");
        p=root;
        while( p ) { printf("\n%d",p->value); p=p->next; };
    
        a = malloc(size*sizeof*a); /* create help array */
        i = 0;
        p=root;
        while( p ) {
          a[i++]=p;
          p=p->next; };
    
        qsort( a, size, sizeof*a, cmp );
        for( i=0; i<size-1; ++i)
          ((Node**)a)[i]->next = a[i+1];
        ((Node**)a)[size-1]->next =0;
    
        puts("Sorted");
        p=a[0];
        free(a); /* free help array */
        while( p ) { printf("\n%d",p->value); p=p->next; };
        ...
    
    /* a Node-compare function to qsort */
    int cmp(const void *a,const void *b)
    {
      return ((*(Node**)a)->value > (*(Node**)b)->value) - ((*(Node**)a)->value < (*(Node**)b)->value);
    }
    Last edited by BillyTKid; 10-26-2010 at 11:30 AM.

  5. #5
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Quote Originally Posted by giove View Post
    you must implement a recursive sorting.
    Starting from the first node, if the i node value is bigger than the i+1 one, you change the next assignement, and so on.
    Terrible advice. Some sorting methods use recursion, but there is absolutely no need to use recursion with every algorithm. The fastest list sorting method I know of doesn't use it.
    Also the i and i+1 suggests something like swapping adjacent items such as in bubble sort. Bubble sort is not at all easy for a linked-list.

    Anass: What you're thinking of is selection sort. The simplest linked-list sorting algorithm is insertion sort.
    Start with two lists, one full of unsorted items and one empty that will contain the sorted items.
    One at a time, take the first item out of the unsorted list, and walk through the sorted list inserting it just before the first node that is larger than it (or at the end if there are none larger than it). Repeat until the unsorted list is empty.
    The same techniques are used for keeping a list sorted.

    BillyTKid: Turning a list into an array and then sorting that instead doesn't teach someone how to do linked-list sorting, it simply teaches a new way of applying array sorting, which the OP may already know.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  6. #6
    Registered User claudiu's Avatar
    Join Date
    Feb 2010
    Location
    London, United Kingdom
    Posts
    2,094
    Learn the merge-sort algorithm and apply it to your problem. Divide and conquer algorithms like merge-sort are a very useful thing to know.
    1. Get rid of gets(). Never ever ever use it again. Replace it with fgets() and use that instead.
    2. Get rid of void main and replace it with int main(void) and return 0 at the end of the function.
    3. Get rid of conio.h and other antiquated DOS crap headers.
    4. Don't cast the return value of malloc, even if you always always always make sure that stdlib.h is included.

  7. #7
    Registered User
    Join Date
    Oct 2010
    Posts
    4
    Thank you guys I'll try your suggestions right now.

  8. #8
    Registered User
    Join Date
    Oct 2010
    Posts
    4
    guys this is what I've done so far:
    Code:
    Node *MakeSortedList(Node *list)
    {
    	//declarations of variables.
    	Node *sorted_list = NULL;
    	Node *temp_node = CreateNode(0,1);
    	int i = 0;
    	
    	//allocating memory for the node.
    	temp_node = (Node *) malloc( sizeof( Node ) );
    	
    	//loop over the list
    	for( i = 0; i < 100; i++ )
    	{
    		while( list->next != NULL )
    		{
    			if( list->value > list->next->value )
    			{
    				temp_node = CreateNode(list->value,1);
    			}
    			list = list->next;
    		}
    		sorted_list = InsertAtBeg(temp_node,list);
    	}
    	
    	return sorted_list;
    }

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Linked List help!!
    By onepuzzledstud in forum C Programming
    Replies: 2
    Last Post: 10-11-2010, 08:36 PM
  2. Circularly-Doubly Linked List implementation
    By BlackOps in forum C Programming
    Replies: 4
    Last Post: 07-19-2009, 04:45 AM
  3. single linked list to double linked list (help)
    By Countfog in forum C Programming
    Replies: 8
    Last Post: 04-29-2008, 08:04 PM
  4. Linked list with two class types within template.
    By SilasP in forum C++ Programming
    Replies: 3
    Last Post: 02-09-2002, 06:13 AM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM