A comparison of Lomuto and Hoare Partitioning Schemes

Posted on Thu 01 September 2016 in algo

I have read before that Hoare Partitioning is faster by a constant factor than the Lomuto Partitioning. This will clearly have an important impact on the performance of Quick Sort. Here, I wanted to check that and see if it holds true in practice, and if so, what that constant factor might be. Let's define the two partitioning schemes below:

Continue reading

Hoare Partitioning and Pivot Selection

Posted on Sun 06 September 2015 in algo

Quicksort is a remarkably flexible algorithm with several variations. Here, I wanted to write about the Hoare partitioning method, in particular, about the special choice of its pivot as the leftmost element. First, lets quickly write down the partitioning algorithm from CLRS exercise 7.1.