Hoare's vs Lomuto's Partition

The basic Lomuto partition scheme swaps the pivot out of the way, does the partition, swaps the pivot into place and then returns an index to the pivot at its sorted position. In this case, the pivot can be excluded from the recursive calls:

The basic Hoare partition scheme scans from both ends towards some point within the partition, putting all elements less than the pivot to the left of all elements greater than the pivot, but any elements equal to the pivot, including the pivot itself, can end up anywhere in the partition, and the index returned is the split point between the left (elements <= pivot) and right (elements >= pivot), so the calling code cannot exclude the element at the index returned from Hoare partition function from recursive calls. If the Hoare scheme is modified to be similar to Lomuto, where it swaps the pivot to either end, does the partition, then swaps the pivot to the split index, then the calling code can exclude the pivot, but this ends up being slower.

Difference between these partitions is not in reqursive calls.

Really any partition (that support correct interface) might be used with the same implementation of the main routine.

Partition functiion usually returns index of pivot. This pivot already stands at the final place. It is not needed to treat this index again.

So for the case when low is included in treatment but highis not, we can write

    pivotindex = partition(arr, low, high); 

    // Separately sort elements before pivotindex and after pivotindex

    quickSort(arr, low, pivotindex); 
    quickSort(arr, pivotindex + 1, high); 

To understand the difference, we also need to focus on the partition method and not just on the calls to quicksort.

Lomuto partition scheme:

algorithm partition(A, lo, hi) is
    pivot := A[hi]
    i := lo
    for j := lo to hi - 1 do
        if A[j] < pivot then
            swap A[i] with A[j]
            i := i + 1
    swap A[i] with A[hi]
    return i

Hoare partition scheme:

algorithm partition(A, lo, hi) is
    pivot := A[lo + (hi - lo) / 2]
    i := lo - 1
    j := hi + 1
    loop forever
        do
            i := i + 1
        while A[i] < pivot

        do
            j := j - 1
        while A[j] > pivot

        if i >= j then
            return j

        swap A[i] with A[j]

(Adding the above as image because I couldn't insert formatted table here. Please click on the image for better view.)

• Also, 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.

I have just mentioned the key differentiating points. I suggest you to read the above two hyperlinks. You might want to gain more knowledge on this topic by reading this.

Comment if you have any further doubts and we will help you solve the doubts.