Analysis of Quicksort with Duplicate Keys

In this post, I will present two slightly different versions of quicksort, and examine why one is better than the other.

Let's dig in the code first.

	#include <vector>
	#include <stdio.h>
	#include <time.h>
	#include <stdlib.h>
	#include <tictoc.h>
	#include <assert.h>
	using namespace std;
	bool isSorted(const vector<int>& array) {
	for (int i=1; i<array.size(); i++)
	if (array[i] < array[i-1]) return false;
	return true;
	}
	void swap(int array[], int i, int j) {
	int temp = array[i];
	array[i] = array[j];
	array[j] = temp;
	}
	void quicksort1(int array[], int left, int right) {
	#ifdef DEBUG
	static int counter = 0;
	counter++;
	printf("#%d quicksort1 with %d,%d\n", counter, left, right);
	#endif
	if (left >= right) return;
	int pivot = left;
	int i = left+1, j = right;
	while (true) {
	while (i < j && array[i] <= array[pivot]) i++;
	while (array[j] > array[pivot]) j--;
	if (i >= j) break;
	swap(array, i, j);
	}
	swap(array, pivot, j);
	quicksort1(array, left, j-1);
	quicksort1(array, j+1, right);
	}
	void quicksort2(int array[], int left, int right) {
	#ifdef DEBUG
	static int counter = 0;
	counter++;
	printf("#%d quicksort2 with %d,%d\n", counter, left, right);
	#endif
	if (left >= right) return;
	int pivot = left;
	int i = left+1, j = right;
	while (true) {
	while (i < j && array[i] < array[pivot]) i++;
	while (array[j] > array[pivot]) j--;
	if (i >= j) break;
	swap(array, i++, j--);
	}
	swap(array, pivot, j);
	quicksort2(array, left, j-1);
	quicksort2(array, j+1, right);
	}
	int main(int argc, char** argv) {
	const int NUM_ELEMENTS = atoi(argv[1]);
	srand(time(NULL));
	vector<int> array(NUM_ELEMENTS);
	int NUM_KEYS = atoi(argv[2]);
	for (int i=0; i<NUM_ELEMENTS; i++)
	array[i] = rand()%NUM_KEYS;
	vector<int> array1(array), array2(array);
	tic();
	quicksort1(&array1[0], 0, NUM_ELEMENTS-1);
	toc();
	assert(isSorted(array1));
	tic();
	quicksort2(&array2[0], 0, NUM_ELEMENTS-1);
	toc();
	assert(isSorted(array2));
	return 0;
	};

view raw qsort_analysis.cpp hosted with ❤ by GitHub

As you can see, the difference between two versions is very subtle. One partitions into two where the left contains values less or equal to pivot key and the right contains values strictly larger. The second version partitions into two where the left contains values less or equal to pivot key and the right contains values greater or equal to the pivot key.

What difference will this make? For an array with distinct keys, the difference is not as significant. However, when we have lots of distinct keys, the story changes. The first one performs extremely poorly when there are many identical keys, whereas the second one performs faster as the number of duplicate keys increases.

$ g++ qsort_analysis.cpp -g -ltictoc -O0 && ./a.out 10000000 10000000
Time elapsed: 2.067320s
Time elapsed: 1.842697s

$ g++ qsort_analysis.cpp -g -ltictoc -O0 && ./a.out 10000000 10000
Time elapsed: 10.985325s
Time elapsed: 1.441884s

How does such subtle difference make such large difference? We can analyze this by looking at an array with all the same keys and observe how many calls each quicksort is called in total.

$ g++ qsort_analysis.cpp -g -ltictoc -O3 -DDEBUG && ./a.out 16 1
#1 quicksort1 with 0,15
#2 quicksort1 with 0,14
#3 quicksort1 with 0,13
#4 quicksort1 with 0,12
#5 quicksort1 with 0,11
#6 quicksort1 with 0,10
#7 quicksort1 with 0,9
#8 quicksort1 with 0,8
#9 quicksort1 with 0,7
#10 quicksort1 with 0,6
#11 quicksort1 with 0,5
#12 quicksort1 with 0,4
#13 quicksort1 with 0,3
#14 quicksort1 with 0,2
#15 quicksort1 with 0,1
#16 quicksort1 with 0,0
#17 quicksort1 with 2,1
#18 quicksort1 with 3,2
#19 quicksort1 with 4,3
#20 quicksort1 with 5,4
#21 quicksort1 with 6,5
#22 quicksort1 with 7,6
#23 quicksort1 with 8,7
#24 quicksort1 with 9,8
#25 quicksort1 with 10,9
#26 quicksort1 with 11,10
#27 quicksort1 with 12,11
#28 quicksort1 with 13,12
#29 quicksort1 with 14,13
#30 quicksort1 with 15,14
#31 quicksort1 with 16,15
Time elapsed: 0.000057s
#1 quicksort2 with 0,15
#2 quicksort2 with 0,7
#3 quicksort2 with 0,3
#4 quicksort2 with 0,1
#5 quicksort2 with 0,0
#6 quicksort2 with 2,1
#7 quicksort2 with 3,3
#8 quicksort2 with 5,7
#9 quicksort2 with 5,5
#10 quicksort2 with 7,7
#11 quicksort2 with 9,15
#12 quicksort2 with 9,11
#13 quicksort2 with 9,9
#14 quicksort2 with 11,11
#15 quicksort2 with 13,15
#16 quicksort2 with 13,13
#17 quicksort2 with 15,15
Time elapsed: 0.000020s

As you can see above, the first version of quicksort is invoked about 2*N times where the second version is invoked about N times for given array of N elements all of equal keys. The reason is that for the first version, each partitioning will be extremely skewed over to the right, whereas for the second version the partition is always at the center, thus leading to much more efficiency.