-
Insertion sort question
Hey all,
I'm doing an assignment, in which I'm reading the contents of a binary file, into a linked-list, which I then need to sort by customer code. At first, I was going to use a bubble-sort on the linked list, but after searching this board, it seemed that an insertion sort would be more appropriate.
However, I think I'm right in saying that I'd need a doubly-linked list to do this? I've only ever used a singly-linked list in the form of a stack, so I'm a little in the dark still. I think this is the correct theory though.
Just wondered if that was right or not and if I need to go and learn how to use a *prev pointer. :)
Thanks,
John.
-
>However, I think I'm right in saying that I'd need a doubly-linked list to do this?
Insertion sort doesn't require a doubly linked list, but you will find that building a new list as you break down the old one is the easiest solution:
Code:
struct node *sort_list ( struct node *in )
{
struct node out = {0,0};
struct node *i, *step, *next;
for ( step = in; step != 0; step = next ) {
next = step->next;
for ( i = &out; i->next != 0; i = i->next ) {
if ( i->next->data > step->data )
break;
}
step->next = i->next;
i->next = step;
}
return out.next;
}
-Prelude
-