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

3-way quicksort

In post Dutch National Flag Algorithm, we discussed how can we sort and 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 that quick sort relies on partitioning of input and input is partitioned in  two parts. What if we divide input space in three parts? Then it becomes 3-way quicksort.

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

Quicksort basics and limitation

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

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

  • 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 partitioned array goes lower than 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 inout array contains lot of duplicate values which is very frequent in real world. Idea is to divide array in three parts rather than two. Let’s say P be pivot. First part contains all numbers which are less than p, second part contains number equal to p and last part contains numbers which are greater than p.

3-way quicksort algorithm 

3-way quicksort is optimization which works in specific cases like when input to be sorted contains few unique keys, in this case having traditional approach of one pivot does not perform well compared to 3-way quicksort.
Some of the properties of 3-way quicksort are:
It is not stable, when stability is the requirement, avoid using quicksort in general.
It uses O(lg(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
Best part is it takes O(n) time when O(1) unique keys.

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

3-way quicksort

3-way quicksort Implementation

#include <stdio.h>

int min(int a, int b){
 if(a > b) 
    return b;
  return a;
}

void swap(int a[], int i, int j){
	int temp = a[i];
	a[i] = a[j];
	a[j] = temp;
}

void quicksort(int a[], int low, int high){
	int pivot = a[high];
	
	int lt = low;
	int reader = low ;
	int gt = high;
	
	while(reader < gt){
		if(a[reader] < pivot){
			swap(a, reader, lt);
			reader++;
			lt++;
		}
		else if(a[reader] == pivot){
			gt--;
		    swap(a, reader, gt);
		}
		else{
			reader++;
		}
	}
  
	int minimum = min( gt-lt, high-gt+1);
	for(int i=0; i<minimum; i++){
		swap(a, lt+i, high-minimum+1+i); 
	}

	if( low < high){
		quicksort(a, low, lt-1);
   		quicksort(a, high-gt+lt, high);
	}
	return ;
}

int main(void) {
	int a[] = {4,3,3,2,7,9,2,3,5,6,7,4};
	int size = sizeof(a)/sizeof(a[0]);

	quicksort(a, 0, size-1);
	
	printf("\n");
	for(int i=0; i<size; i++){
		printf("%d ", a[i]);	
	}

	return 0;
}

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.