• 10-26-2010
Anass
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!
• 10-26-2010
giove
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.
• 10-26-2010
Prelude
>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.
• 10-26-2010
BillyTKid
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); }```
• 10-26-2010
iMalc
Quote:

Originally Posted by giove
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.
• 10-26-2010
claudiu
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.
• 10-27-2010
Anass
Thank you guys I'll try your suggestions right now.
• 10-27-2010
Anass
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; }```