Computer Programming

» Guy Lecky-Thompson - Sorting linked list

The short answer is that you might like to try here:

http://computerprogramming.suite101.com/...

The basic premise for bubble sorting a liked list is that you want to swap the pointers of each element, and not try to make a copy of every node. This is the advantage of using a linked list over an array of structs.

So, each pair of nodes has to have their data member evaluated (compared), and then the pointer magic takes over.

Let's say we have nodes A C B D in a linked list. A points to C, points to B, points to D.

We want to sort the list, so we go through comparing the letters. A is 'less' than 'C', so we don't swap. However, 'C' is 'more' than 'B', so we need to swap the nodes.

To do this, we point A to B, then C to D, and finally B to C. You'll have to store a reference somewhere to avoid losing the links.

Finally, to complete the routine, don't forget to keep swapping until no more swaps have been done. It's not sufficient just to go through the whole list once. It will likely take a few 'passes'.

That link again -
http://computerprogramming.suite101.com/...

Regards,
Guy