1. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
Sep 2012
Posts
13
Rep Power
0

Code:
```Gll * fun_s(Gll* node,comp_fun comp )
{
if(!node || !(node -> next) ){
printf("less than two node in the list\n");
return node;
}
//int ints[] = {12,2,3,4,5,6,1,8,9,10,11,7};
//int ints[] = {1,12,2,3,5,8,4,9,6,10,11,7};
while ( 1 ){

Gll *prev,*curr,*nxt ;
int swap = 0;
prev = curr = node ;
nxt = curr->next;
while( nxt ) {
if ( (*comp)(curr->data ,nxt->data) > 0) {
curr -> next = nxt -> next;
nxt -> next = curr;
if(curr == node){
prev = node = nxt;
}else{
prev -> next = nxt;
prev = nxt ;
}
swap = 1;
}else {
prev = curr;
}
curr = prev -> next ;
nxt = curr -> next;

}
if(!swap)
break;
}
return node;
}```
This is program which sorts a linked lists if its unsorted and retains
the same if its sorted.

But the program is not so efficient in the sense that its kind of bubble
sort.In every iteration the next highest element will get sorted out.
But i am not able have a mechanism which can reduce the no of iterations.
That means there is no need to check for already sorted elements.

Please suggest if any other best or optimised mechanism is available.

Also please let me know if you find any problem( does not work for any combination of input)
2. No Profile Picture
Contributing User
Devshed Intermediate (1500 - 1999 posts)

Join Date
Feb 2004
Location
San Francisco Bay
Posts
1,939
Rep Power
1317
Bubblesort is one of the worst sorting algorithms, either for arrays or for linked lists. Mergesort, on the other hand, is a pretty good option for sorting a linked list:

- doesn't require random access
- O(n*log(n)) worst case
- doesn't require allocating extra memory

The algorithm:

1. Divide the list in the middle into two lists of close-to-equal size.
2. Recursively sort the two lists.
3. Merge the sorted lists into a single sorted list.
3. No Profile Picture
bdb
Contributing User
Devshed Newbie (0 - 499 posts)

Join Date
Aug 2012
Posts
156
Rep Power
37
One option is to copy the list to an array, sort the array (using qsort), and copy back to the list.
4. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
Sep 2012
Posts
13
Rep Power
0
Thanks for the replies.
Yeah, i understand.
Before asking here i just googled, many people suggested only these two methods.

I am going to try for any one of these methods.