Explanation of Hoare Partitioning algorithm

Question

As per the pseudo-code given in many websites, I have written this Hoare partitioning algorithm, which takes an array, the start and end indexes of the sub-array to be partitioned based on the pivot given. It works fine, but can somebody explain the logic, how it does what it does? Here' the code:

def hoare(arr,start,end):
     pivot = 4
     i,j = start,end
     while i < j:
        while i < j and arr[i] <= pivot:
            i += 1
        while j >= i and arr[j] > pivot:
            j -= 1
        if i < j:
            arr[i],arr[j] = arr[j],arr[i]
     return j    

There's another variant of the partitioning, the Lomuto algorithm. It does something similar, although since I don't understand the Hoare algorithm in the first place, I can't spot the difference. Can anybody explain what's going on in the algorithm, and which one gives a better performance in which case?

Answer 1

I'd suggest simulating this using a deck of cards and two pawns / coins to represent i and j. Basically, the algorithm accomplishes these two things, simultaneously:

• Find where the array should be split up to have the correct amount of "buckets" to the left and to the right of this position. This is done by the values of i and j meeting in the "middle" of the partition.
• Move the array elements to either left, or the right of the middle, depending on whether they're lesser and greater than the pivot.

This means that at any time, i is either at the middle or left of it. The converse is true for j. Knowing this, one can see that what the while loops do is find an element that's to the left of the middle but should be on the right, and vice versa. That is, find two elements that are in the wrong half. These are then swapped.

When i and j meet in the middle, to the left you have either elements that were skipped by the while, because they're smaller than pivot; or elements that were swapped from the other side, and are thus also smaller than pivot. (Vice versa for the elements right of the middle.)

A possible source of confusion is that a zero-based array index can be thought to either point at an element, or to point between two elements. E.g. the index 0 basically means "between the 'zeroth' and the first element in the array", and when you're accessing an element, you take the one following this position - making array[0] result in what's intuitively the first element of the array.

Answer 2

Both Hoare and Lamuto are partition algorithms. A partition algorithm moves things around in an array so that everything smaller than a certain element ends up on one side and everything larger on the other. This can be used to quickly sort an array or to find the median.

Hoare works by moving two boundaries towards the middle, one from the left and one from the right. The following steps are done in a loop:

1. The left boundary moves until it reaches something larger than the chosen element.
2. The right boundary moves until it reaches something smaller than the chosen element.
3. If the boundaries haven't crossed, the two are swapped.

This process is repeated until the boundaries meet in the middle. The result is a partition with everything less on the left and everything greater on the right.

Lomuto is a similar process but uses only one boundary (usually going up from the left). This makes it easier to implement, but somewhat slower (larger constant terms with the same asymptotic complexity).