Implementation of QuickSort to handle duplicates

Question

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.

Answer 1

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.