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.

Advertisements

Pages: 1 2