This is an past year question for a school exam that I do not suggested solutions for.
Quick Sort is not stable because of need to swap values in array when partition is done. If we store the values to be sorted in a linked list, we can make quick sort stable. Also, we can easily improve the performance of Quick Sort by grouping all the values that are equal to the pivot to the middle so they do not need to be considered during the subsequent partitions. Consider the following code.
function ListNode quickSort(ListNode head) partition(params1) ListNode front = quickSort(params2) ListNode middle = params3 ListNode back = quickSort(params4) return combine(front,middle,back)
Identify what should be
Use pseudocode to describe the partition method. Make sure that special cases such as when there is a null in parameter is taken care of. Also, the new version of QuickSort is in-place.
I think that quickSort should return the
head node of the list, but then middle seems strangely placed in the code as I would think of putting it after after partition. Also, I do not know the pseudocode standards for linked list and whether it is similar to the case of the normal one done with arrays. Can anyone help me with this?