Quicksort

Lomuto partition:

def lomuto(arr, low, high):
    
    # choose last element as pivot
    pivot = arr[high] 
    
    # pointer i tracks where to place pivot
    i = low

    # pointer j iterates through array
    for j in range(low, high):
        
        # If current element is smaller than pivot
        if (arr[j] < pivot):
            
            # swap array[i] and array[j]
            array[i], array[j] = array[i], array[j]
            i += 1
    # swap pivot and array[i]
    arr[i], arr[high] = arr[high], arr[i]
    return (i)

Hoare’s partition:

def hoares(arr, low, high):

    # choose last element as pivot
    pivot = arr[high]
    a = low
    b = high - 1

    while True:

        # Move a right until value > pivot
        while a <= b and (arr[a] < pivot):
            a += 1

        # Move b left until value < pivot
        while a <= b and (arr[b] > pivot):
            b -= 1
        if (a < b):
            # Swap values
            arr[a], arr[b] = arr[b], arr[a]
        else:
            # Break out if pointers met
            break
    # Swap pointer with pivot
    arr[a], arr[high] = arr[high], arr[a]
    return a

Quicksort algorithm

def quicksort(arr, left, right)
    if (left < right):
        pivot = partition(arr, left, right)
        quicksort(arr, left, pivot-1)
        quicksort(arr, pivot+1, right)

Comparison:

Hoare’s better performance and efficiency than Lomuto.

But Lomuto’s uses a single pointer compared to Hoare’s double pointer, so Loumto’s is simpler.

It may be better to use Lomuto’s if Hoare’s has insignificant efficiency gain.