Computer Programming

» eureka5720 - Sorting linked list

I would like to sort my linked list using the method of bubble sort in C programming, which will enable me to sort the every node in the linked list. How can i do that? Anyone have skeleton of the program can share?

Thank you.

-- posted by eureka5720

» 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