The Shed is going Social! Join us on FaceBook and Twitter and chime in on the conversation.
|
 |
|
Dev Shed Forums
> Programming Languages
> C Programming
|
Linked list sorting
Discuss Linked list sorting in the C Programming forum on Dev Shed. Linked list sorting C programming forum discussing all C derivatives, including C#, C++, Object-C, and even plain old vanilla C. These languages are low level languages, and used on projects such as device drivers, compilers, and even whole computer operating systems.
|
|
 |
|
|
|
|

Dev Shed Forums Sponsor:
|
|
|

September 20th, 2012, 11:31 PM
|
|
Registered User
|
|
Join Date: Sep 2012
Posts: 13
Time spent in forums: 3 h 34 m 57 sec
Reputation Power: 0
|
|
|
Linked list sorting
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)
|

September 21st, 2012, 01:04 AM
|
|
Contributing User
|
|
Join Date: Feb 2004
Location: San Francisco Bay
|
|
|
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.
|

September 21st, 2012, 04:03 AM
|
|
|
|
One option is to copy the list to an array, sort the array (using qsort), and copy back to the list.
|

September 22nd, 2012, 08:38 PM
|
|
Registered User
|
|
Join Date: Sep 2012
Posts: 13
Time spent in forums: 3 h 34 m 57 sec
Reputation 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.
|
Developer Shed Advertisers and Affiliates
| Thread Tools |
Search this Thread |
|
|
|
| Display Modes |
Rate This Thread |
Linear Mode
|
|
Posting Rules
|
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts
HTML code is Off
|
|
|
|
|