Hoare’s Partition
October 28, 2016
I’ve recently rekindled my interest in sorting algorithms (it’s a fascination that never really goes away), and I’ve been looking at quick sort. The most common academic version of quick sort uses a partition due to Nick Lomuto, which takes a single pointer that scans through the arry, concludes with the partitioning element in the middle, all the less-than items to its left, and all the greater-than items to its right, then recurs on the two halves; the partitioning element is never part of any subsequent recursive call in the quick sort.
The original partitioning algorithm by C. A. R. Hoare works differently, with two pointers instead of one. One pointer starts at the left end of the array, and is advanced until it finds an item out of place. The other pointer starts at the right end of the array, and marches to the left end of the array until it finds an item out of place. Then the array items are swapped, each pointer takes one step toward the other, and the process continues, stopping when the two pointers cross, at which time there is a final swap. Hoare’s partition concludes by returning the right-side pointer; all items to the left of the pointer, plus the item at the pointer itself, are smaller than all items to the right of the pointer. The partitioning element is somewhere in the left-hand partition, but not necessarily at its end, which requires a change to the recursive call in the quick sort algorithm, which includes the partitioning element.
Your task is to implement Hoare’s partition and use it to write a quick sort program. 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 
Found this code on Stackexchange. I found it to be quite fast. Source code is in D…
void QuickSort(int[] a, int start, int end) { if (end <= start) return; int q = HoarePartition(a, start, end); QuickSort(a, start, q); QuickSort(a, q + 1, end); } int HoarePartition (int[] a, int p, int r) { int x = a[p], i = p-1, j = r+1; while (1) { do j--; while (a[j] > x); do i++; while (a[i] < x); if (i < j) swap(a[i], a[j]); else return j; } }I did a little speed comparison with some implementations of Quicksort. I took the code which I’d posted earlier on PP, and also three implementations from Rosetta Code (https://www.rosettacode.org/wiki/Sorting_algorithms/Quicksort#D). Here’s the code in D:
import std.stdio; import std.datetime; import std.algorithm; import std.random; import std.range; import std.array; void quickSort1(T)(T[] items) pure nothrow @safe @nogc { if (items.length >= 2) { auto parts = partition3(items, items[$ / 2]); parts[0].quickSort1; parts[2].quickSort1; } } auto quickSort2(T)(T[] items) pure nothrow @safe { if (items.length < 2) return items; immutable pivot = items[0]; return items[1 .. $].filter!(x => x < pivot).array.quickSort2 ~ pivot ~ items[1 .. $].filter!(x => x >= pivot).array.quickSort2; } T[] quickSort3(T)(T[] items) pure nothrow { if (items.empty) return items; T[] less, notLess; foreach (x; items[1 .. $]) (x < items[0] ? less : notLess) ~= x; return less.quickSort3 ~ items[0] ~ notLess.quickSort3; } void hoareQuicksort(T)(T[] a, size_t start, size_t end) { if (end <= start) return; size_t q = hoareQSPartition(a, start, end); hoareQuicksort(a, start, q); hoareQuicksort(a, q + 1, end); } size_t hoareQSPartition(T)(T[] a, size_t p, size_t r) { size_t x = a[p], i = p-1, j = r+1; while (1) { do { j--; } while (a[j] > x); do { i++; } while (a[i] < x); if (i < j) swap(a[i], a[j]); else return j; } } void main() { const size_t N = 10_000_000; size_t[] test = new size_t[](N); for (size_t k = 0; k < N; k++) { test[k] = uniform(1, N); } StopWatch q1, q2, q3, q4; q1.reset; q1.start; quickSort1(test.dup); q1.stop; q2.reset; q2.start; quickSort2(test.dup); q2.stop; q3.reset; q3.start; quickSort3(test.dup); q3.stop; q4.reset; q4.start; hoareQuicksort(test.dup, 0, N-1); q4.stop; writefln("%d elements\n", N); writefln("Quicksort #1 took %d ms", q1.peek.msecs); writefln("Quicksort #2 took %d ms", q2.peek.msecs); writefln("Quicksort #3 took %d ms", q3.peek.msecs); writefln("Quicksort Hoare took %d ms", q4.peek.msecs); }Compiled with [i]dmd -O -release -inline -of”qsort” “qsort.d”[/i] it gives these times…
Compiled with [i]ldc2 -O3 -enable-inlining -of”qsort” “qsort.d”[/i] it gives these times…
Maybe there’s an even faster implementation….
Here’s a solution in C. I had some bugs in my initial implementation that I’ve fixed, but I’m still not feeling confident that this works properly, as I haven’t done much testing. In practice, I’ve used Lomuto partitioning when implementing quicksort. IIRC, I implemented quicksort since I needed to track where each item an unsorted array was placed in the sorted array (this also could have been figured out *after* sorting, but would have been O(n^2), so I tracked it at sort-time).
#include <stdio.h> void print_array(int* array, int n) { printf("["); for (int i = 0; i < n; ++i) { if (i > 0) printf(","); printf("%d", array[i]); } printf("]"); } void swap(int* a, int* b) { int tmp = *a; *a = *b; *b = tmp; } int partition(int* array, int n) { int pivot = array[0]; for (int i = 1, j = n-1;; ++i, --j) { while (i < n && array[i] < pivot) ++i; while (j >= 0 && array[j] > pivot) --j; if (i >= j) { swap(array, array + j); return j; } swap(array + i, array + j); } } void qsort(int* array, int n) { if (n <= 1) return; int p = partition(array, n); qsort(array, p); qsort(array + p + 1, n - p - 1); } int main() { int array[] = {9,4,8,7,1,7,4,10,1,5,5,5,8,4,8,5,1,2,8,5}; int n = sizeof(array) / sizeof(int); printf("array (unsorted):\n "); print_array(array, n); printf("\n"); qsort(array, n); printf("array (sorted):\n "); print_array(array, n); printf("\n"); }Output:
> “IIRC, I implemented quicksort since I needed to track where each item an unsorted array was placed in the sorted array (this also could have been figured out *after* sorting, but would have been O(n^2), so I tracked it at sort-time).”
I suppose that using a hash table could have worked as well for what I was trying to do (create a mapping of item to index), but I don’t recall the details, and may not have had hash tables available or even a standard library sorting algorithm. I was using VBA (Visual Basic for Applications) to write a Microsoft Office plugin. It had to run on both Windows and Mac, so some of the Windows-only extensions weren’t available.
[…] 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 […]
[…] two previous exercises we’ve been working toward a variant of quicksort that has guaranteed O(n log n) […]
[…] 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 […]