1
$\begingroup$

This is an past year question for a school exam that I do not suggested solutions for.

Problem Description

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)

Task

Identify what should be params1,params2,params3,params4

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?

Improve this question
$\endgroup$
2
  • $\begingroup$ putting [middle] after after partition I cannot understand that. (It took me a while, anyway, to see that the structure proposed might work with Lomuto partition.) $\endgroup$
    – greybeard
    Commented Mar 9, 2019 at 6:35
  • $\begingroup$ Grouping the values equal to the pivot is certainly counterproductive. Because even if there are many equal keys, the pivot may still be different. But you will pay the overhead of handling three lists instead of two anyway (two comparisons per element instead of one). Unless the input is very special, my bet is a degradation of the performance. $\endgroup$
    – user16034
    Commented Jul 18, 2023 at 7:29

1 Answer 1

Reset to default
1
$\begingroup$

The point is that with linked lists you can reorganize them in-place. So, your partition method should return three separate lists: lower, middle and higher. Each list contains nodes from source list, only pointers are manipulated.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.