Quick Sort using Hoare’s Partitioning scheme

Implement Quicksort 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.

 
C++ implementation –
 

Download   Run Code

Output:

-50 -40 -38 -29 -9 -6 2 9 15 23 29 36 36 39 49

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

 
Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂