3-way quicksort (Quick sort on non unique elements)

In the post on the Dutch National Flag Algorithm, we discussed how to sort an array in linear time by partitioning it in four parts, red, white, unknown and blue. Can we apply the same technique on quick sort.? As we all know, quick sort relies on the partitioning of input into two parts. What if we divide the input into three parts? Then it becomes a 3-way quicksort.

The 3-way partition variation of quick-sort has a slightly higher overhead compared to the standard 2-way partition version. Both have the same best, typical, and worst-case time bounds, but the 3-way version is highly adaptive in the very common case of sorting with many non-unique keys.

Quicksort basics and limitation

Before going ahead with 3-way partition method, I would strongly recommend that you go through the usual quick sort algorithm: Quicksort algorithm in C

A big limitation of quicksort is that it has O(n2) worst-case running time. Some improvements have been suggested as given below:

  • The cutoff to insertion sort. Switch to insertion sort for arrays with size less than a pre-decided limit. We follow quick sort and partition array. Once the size of the partitioned array goes lower than the limit, apply insertion sort on that array. Limit varies from system to system and typically it is between 5 to 15.
  • Median-of-three partitioning. Use median of a small sample of items taken from the array as the partitioning item. Doing so will give a slightly better partition but at the cost of computing the median.

There is another optimization which is called as Entropy-optimal sorting or 3-way partition quick sort. This method is useful when the input array contains a lot of duplicate values which can be frequently seen in the real world. The idea is to divide the array in three parts rather than two. Let’s say P is the pivot index. The first part contains all the numbers which are less than P, the second part contains number equal to P and the last part contains numbers which are greater than P.

3-way quicksort algorithm 

Some of the properties of the 3-way quicksort are:
It is not stable! Avoid using quicksort in cases where stability is essential.
It uses O(log(n)) extra space, why? Because of the recursion.
Worst case run time is as same as classic quicksort, O(n2), but typically O(nlog(n)) time
The best part is that it takes O(n) time when O(1) unique keys.

This algorithm partitions the array into three parts:
1. one with is less than pivot
2. equal to pivot
3. one with elements greater than the pivot

3-way quicksort

3-way quicksort Implementation

 
import java.util.Arrays;
import java.util.Stack;
 
/**
 * Created by sangar on 18.9.18.
 */
public class StockSpan {
    public static int[] stockSpan(int[] prices){
 
        Stack<Integer> s = new Stack();
        int[] span = new int[prices.length];
 
        //Step 1. Initialization
        span[0] = 1;
        s.push(0);
 
        for(int i=1; i<prices.length; i++){
            //Find the price on stack which is greater than current day's price
            while(!s.empty() && prices[i] > prices[s.peek()])
                s.pop();
 
            if(s.empty())
                span[i] = i+1;
            else
                span[i] =  i - s.peek();
 
            //Push current day onto top of stack
            s.push(i);
        }
 
        return span;
    }
 
    public static void main(String args[]){
        int prices[] = {100, 60, 70, 65, 80, 85, 45, 77, 56, 98, 200};
        int[] span = stockSpan(prices);
 
        Arrays.stream(span).forEach(System.out::println);
 
    }
}

The complexity of 3-way quicksort is O(n2).

Please share if something is wrong or any other suggestion or query. We would love to hear what you have to say.