I'm sorry, but I can't find your question anywhere in that post. All I see is an exercise (from a book?). But I'll humor you and offer some suggestions:
>the list must be sorted in place.
If you mean by not using any extra memory then it's hard not to sort a list in place. If you mean by performing exchanges within the same list then you're going about it in an inefficient way. You'll find sorting a list easier if you build a new list from the old one by removing from the old list and adding the removed item in sorted position to the new list.
That would be how you perform insertion sort easily with linked lists, and mergesort. It's also possible (thought slightly more difficult and with annoying degenerate cases) to use binary search tree insertion and traversal routines to sort a linked list without using any extra memory:
Code:
#include <stdio.h>
#include <stdlib.h>
struct node {
int data;
struct node *prev, *next;
};
static struct node *treeinsert ( struct node *tree, struct node *item )
{
if ( tree == NULL ) {
tree = item;
}
else if ( item->data < tree->data ) {
tree->prev = treeinsert ( tree->prev, item );
}
else {
tree->next = treeinsert ( tree->next, item );
}
return tree;
}
static void traverse ( struct node *tree, struct node **list )
{
struct node *save;
if ( tree == NULL ) {
return;
}
traverse ( tree->next, list );
save = tree->prev;
tree->prev = NULL;
tree->next = *list;
if ( *list != NULL ) {
(*list)->prev = tree;
}
*list = tree;
traverse ( save, list );
}
struct node *treesort ( struct node *list )
{
struct node *tree = NULL;
struct node *save;
while ( list != NULL ) {
save = list->next;
list->prev = list->next = NULL;
tree = treeinsert ( tree, list );
list = save;
}
traverse ( tree, &list );
return list;
}
int main ( void )
{
struct node *list = NULL;
struct node *n;
int i;
for ( i = 0; i < 10; i++ ) {
n = malloc ( sizeof *n );
if ( n == NULL ) {
break;
}
n->data = rand() % 10;
n->prev = NULL;
n->next = list;
if ( list != NULL ) {
list->prev = n;
}
list = n;
}
printf ( "Unsorted\n" );
for ( n = list; n->next != NULL; n = n->next ) {
printf ( "%d->", n->data );
}
printf ( "%d\n", n->data );
for ( ; n != NULL; n = n->prev ) {
printf ( "%d%s", n->data, n->prev == NULL ? "\n" : "->" );
}
list = treesort ( list );
printf ( "Sorted\n" );
for ( n = list; n->next != NULL; n = n->next ) {
printf ( "%d->", n->data );
}
printf ( "%d\n", n->data );
for ( ; n != NULL; n = n->prev ) {
printf ( "%d%s", n->data, n->prev == NULL ? "\n" : "->" );
}
return 0;
}
There are a few advantages to this approach:
1) You can easily sort a double linked list without jumping through hoops.
2) The code is easily accessable to anyone familiar with simple binary search trees.
3) For random data, it's every bit as efficient as sophisticated sorts (O(n log n))
4) It's easy to write. What I posted was the first try, and it compiled/ran correctly the on the first compile.
There is a big disadvantage too.
1) If the list is already sorted, the performance of the tree slows the sort down considerably.
I don't really recommend such a beast because mergesort is better, but this should get you started.