Hoare’s Partition, Improved
November 1, 2016
In today’s exercise we will make several improvements to the quicksort program of the previous exercise, working in small steps and measuring our progress throughout. We make the following improvements:
- Move the swap and comparison inline.
- Early cutoff and switch to insertion sort.
- Improved pivot with median-of-three.
All three improvements are well-known. The first improvement eliminates unneeded function-calling overhead. The second improvement reduces the number of recursive calls on very small sub-arrays, replacing them with a sorting algorithm that is well-adapted to nearly-sorted arrays. The third improvement improves the likelihood of a good partition and eliminates some cases where the algorithm performs poorly.
Your task is to write an improved quicksort and measure your improvement. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 
Here’s a solution in C99. Compiler optimizations were disabled. Each improvement was added successively. I didn’t look at how each one improves performance in isolation.
For each experiment, I sorted 50,000 random arrays, each with 1,000 elements.
The unoptimized version took 6.506 seconds.
Adding Inlined swapping reduced the time to 5.392 seconds.
Using insertion sort for arrays with 21 or fewer items reduced the time to 4.703 seconds. I manually tuned the size of arrays for early cutoff.
Adding median-of-three for determining a pivot reduced the time to 4.653 seconds.
The following code (and corresponding output) includes all the improvements.
#include <stddef.h> #include <stdio.h> #include <stdlib.h> #include <time.h> void insertionsort(int* array, size_t n) { for (int i = 1; i < n; ++i) { for (int j = i; j > 0 && array[j-1] > array[j]; --j) { int tmp = array[j]; array[j] = array[j-1]; array[j-1] = tmp; } } } int partition(int* array, size_t n) { int pivot = array[0]; // improvement 3: median-of-three if (n >= 3) { int sample[3]; for (int i = 0; i < 3; ++i) sample[i] = array[i]; insertionsort(sample, 3); pivot = sample[1]; } int i = -1; int j = n; while (1) { do { ++i; } while (array[i] < pivot); do { --j; } while (array[j] > pivot); if (i >= j) return j; // improvement 1: inline swap int tmp = array[i]; array[i] = array[j]; array[j] = tmp; } } void quicksort(int* array, size_t n) { if (n < 2) return; // improvement 2: early cutoff to insertion sort if (n < 22) { insertionsort(array, n); return; } int p = partition(array, n); quicksort(array, p + 1); quicksort(array + p + 1, n - p - 1); } void init_random_array(int* array, size_t n) { for (int i = 0; i < n; ++i) { array[i] = rand(); } } int main(void) { srand(time(NULL)); size_t n = 1000; int loops = 50000; clock_t tic = clock(); for (int i = 0; i < loops; ++i) { int array[n]; init_random_array(array, n); quicksort(array, n); } clock_t toc = clock(); double elapsed = (double)(toc-tic) / CLOCKS_PER_SEC; printf("Elapsed Time: %f\n", elapsed); return 0; }Output:
[…] two previous exercises we’ve been working toward a variant of quicksort that has guaranteed O(n log n) performance; […]
[…] sorting algorithm that we have been working up to in three previous exercises is introspective sort, or introsort, invented by David Musser in 1997 for the C++ […]