Implement QuickSort to sort singly linked list. The function will return the head of the sorted list:


i think
1. it should implement it as recursive function to simplify the code.
2. it has to use pivot to connect left and right sub lists. To make it work, it’ll need to append pivot to the end of left sub list, and make sure after sorted the list still keeps pivot at the end of the list in the case of multiple items that have the same value as pivot.

we know that
Quick sort works in following steps:

1. Pick an item from unsorted collection.
2. Split the collection such that all items with value less than pivot go to left set, and all items with value greater or equal to pivot values go to right set.
3. Sort left set and right set.
4. Connect left set, pivot and right set to form sorted collection: left set + pivot + right set.

Most of the time just posting an assignment and saying something like, "I don't know how to do it," will not get a helpful response. The idea is that you use what you learned in class or in some previous class to start the program. If (when) you get to a part that doesn't work the way you expect or if you write and test part of the code but are stuck for ideas about how to proceed, then.

1. Post the code that you have so far.

2. Ask specific questions about parts that you don't understand.

Like this: "When I tried to compile the program, the compiler gave the following message(s) that I didn't understand: ...

or

Like this: "The program compiled without any warning or error messages, but then I gave the program the following input:... I expected the following output:..., but the program (crashed) (gave the following wrong output..) (whatever...)"



Regards,

Dave

Footnote: since the assignment involves sorting a linked list of NODE objects, you also have to implement (and populate) such a thing before you can sort it. If you already know how to do that, good, but if you are going to post any code for sorting a list, you should also show the code that gets values into the list (and show what you expect the output to be before and after the sort routine.)