Quick Sort on list using Struct

[DSE7X9L8]

Implement the quicksort algorithm on lists. You write one function
struct listnode * sort(struct listnode * a);
with
struct listnode { struct listnode * next; int key;};
It takes a list, and returns the list in sorted sequence. You change only pointers, do not allocate new nodes or move key values to different nodes. The programming language is C or C++; test your code before submission using the gcc or g++ compiler

[MikeyBoy]

And?

[dhayden]

- Create a vector of pointers to the nodes in the list.
- Sort the vector based on the nodes that the items point to.
- Change the head and next pointers of the nodes to match the vector.

[Duthomhas]

Quicksort is not typically suited to sorting linked lists; nevertheless, it remains (for inexplicable reasons) a popular CS homework.

I recommend a recursive algorithm. Each iteration should create two (or three) new list heads: one for items before the pivot and one for items after the pivot (and possibly one for items equal to the pivot).

Partitioning is simply a matter of traversing the list and appending (moving) items to the new lists. Since you are using a singly-linked list, you might also want to keep track of the tail of each new list.

Chose (as pivot) the first item in the list.


The other option, less expensive in terms of memory but more expensive in terms of time, is to have a function that returns node N in a list:

struct listnode* get_nth_node( struct listnode* first, int n );

You can then treat the list very much like an indexed array (and follow the standard quicksort stuff you'll find online).

Chose any item you wish as pivot.


Hope this helps.