November 1, 2016 9:00 AM
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:
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.
Posted by programmingpraxis
Categories: Exercises
Tags:
Mobile Site | Full Site
Get a free blog at WordPress.com Theme: WordPress Mobile Edition by Alex King.
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:
By Daniel on November 7, 2016 at 6:54 AM
[…] two previous exercises we’ve been working toward a variant of quicksort that has guaranteed O(n log n) performance; […]
By A Median-Of-Three Killer Sequence | Programming Praxis on November 8, 2016 at 9:01 AM
[…] 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++ […]
By Introspective Sort | Programming Praxis on November 11, 2016 at 9:02 AM