1
$\begingroup$

I have this past year question based on the following scenario:

When the list of items to be sorted contains a lot of duplicate values, we can improve QuickSort by grouping all the values that are equal to the pivot to the middle and then we recursively QuickSort those values on the left and those values on the right. Make the necessary changes to the partition method to achieve that.

Here is the implementation of Quicksort, written in Java. I will not include the code in the main page because it seems that this site requests for description of pseudocode rather than actual code, even if the code is very “simple”.

In particular, this quicksort implementation is similar to the typical one, but choses its pivot on the left of the array.

I have some basic understanding of the quicksort algorithm based on the actual code, but a lot of times I have to break down the code myself to understand it. Whenever I am given pseudocode hints to understand the algorithm[and to be honest I don’t know sometimes whether a hint is a very obvious one or a rather implicit one], I somehow cannot appreciate the “magic” behind the pseudocode.

My understanding of this implementation of quicksort is that the array has to be iterated to make 2 regions of low and high values, while we dynamically decide on where to put the pivot, call it position X, which in this implementation is chosen to be the leftmost element of the input array. If this position X is dynamically decided, how exactly do you “group elements equal to pivot” to middle, and how exactly does it adhere to the principles behind the typical algorithm?

Do inform me if more information is required or the formatting of the question doesn't adhere to the standards here.

$\endgroup$
  • $\begingroup$ What is your understanding? Do you think the implementation you linked is handling the case for duplicates or do you want to know how to modify this implementation to handle duplicates? $\endgroup$ – Navjot Waraich Feb 25 at 7:57
  • $\begingroup$ I want to know how to modify this implementation to handle duplicates, and this current implications isnt optimised for that reason $\endgroup$ – Prashin Jeevaganth Feb 25 at 12:39
2
$\begingroup$

The simple implementation idea is to separate the values into three groups: values less than the pivot, values equal to the pivot, and values greater than the pivot.

In pseudocode, the algorithm looks like the following.

algorithm quicksort(A, lo, hi):
    if lo < hi then
        p ← pivot(A, lo, hi)
        left, right ← three-way-partition(A, p, lo, hi) 

        quicksort(A, lo, left - 1)
        quicksort(A, right, hi)

The partition procedure looks like the following.

procedure three-way-partition(A, pivot, lo, hi):
    l ← lo
    r ← lo
    u ← hi

    while r ≤ u:
        if A[r] < pivot:
            swap A[l] and A[r]
            l ← l + 1
            r ← r + 1
        else if A[r] > pivot:
            swap A[r] and A[u]
            u ← u - 1
        else: // the element is equal to pivot
            r ← r + 1
    return l, r

It uses three indices l, r and u (left, right, and upper bound), maintaining the following invariant in the while loop.

  • lo ≤ l ≤ r ≤ u ≤ hi
  • the elements with index in [lo, l) are smaller to the pivot.
  • the elements with index in [l, r) are equal to the pivot.
  • the elements with index in [r, u] are not examined yet.
  • the elements with index in (u, hi] are greater than the pivot.

There are a few minor variants. The above should be enough for you to understand what is going on.

$\endgroup$
  • $\begingroup$ Thanks, I understood your answer, but I still have this general question of understanding a hint of pseudocode from any question prompt and algorithm design in general. Just how do you think of such things from a typical implementation. $\endgroup$ – Prashin Jeevaganth Feb 25 at 14:34
  • $\begingroup$ That question of how to think is indeed very general. Experience. Patience. Persistence. Good textbooks. Lots of practice. The relevant technique here is the usage of pointers to compute and define regions. It will be enough and excellent for you if you can appreciate the idea of bookkeeping pointers here. $\endgroup$ – Apass.Jack Feb 25 at 14:42
  • $\begingroup$ @PrashinJeevaganth it is the three way quicksort using the Dutch national flag algorithm. You can learn about it more. $\endgroup$ – Navjot Waraich Feb 25 at 14:43
  • $\begingroup$ @Apass.Jack do u have a recommendation for other textbooks? I'm currently using Introduction to Algorithms by Thomas H. Cormen $\endgroup$ – Prashin Jeevaganth Feb 25 at 14:45
  • $\begingroup$ @PrashinJeevaganth That book is one of my favorites. Concentrate on that one for some time. $\endgroup$ – Apass.Jack Feb 25 at 14:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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