# Quick sort algorithm using Hoare’s Partitioning scheme

Implement Quick sort algorithm using Hoare’s Partitioning scheme.

As Lomuto partition scheme is more compact and easy to understand, it is frequently used in partition process of Quicksort. But this scheme degrades to O(n2) when the array is already sorted as well as when the array has all equal elements. In this post, much more efficient Hoare partition scheme is discussed.

### Hoare partition scheme:

Hoare uses two indices that start at the ends of the array being partitioned, then move toward each other, until they detect an inversion: a pair of elements, one greater than the pivot, one smaller, that are in the wrong order relative to each other. The inverted elements are then swapped. When the indices meet, the algorithm stops and returns the final index.

Hoare’s scheme is more efficient than Lomuto’s partition scheme because it does three times fewer swaps on average, and it creates efficient partitions even when all values are equal. But like Lomuto’s partition scheme, Hoare partitioning also causes Quicksort to degrade to O(n2) when the input array is already sorted; it also doesn’t produce a stable sort.

Note that in this scheme, the pivot’s final location is not necessarily at the index that was returned, and the next two segments that the main algorithm recurs on are [low..pivot] and [pivot+1..high] as opposed to [low..pivot-1] and [pivot+1..high] as in Lomuto’s scheme.

## Java

Output:

[-6, -3, 1, 2, 3, 5, 6, 8, 9]

References: https://en.wikipedia.org/wiki/Quicksort

(1 votes, average: 5.00 out of 5)

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂