Question

Explain what happens in the Lomuto partition when there is a lot of the same elements in the input and justify the consequences it has for the time complexity of Quicksort.

Answer 1

Lomuto’s Partition Scheme

This scheme chooses a pivot that is typically the last element in the array. The algorithm maintains index i as it scans the array using another index j such that the elements lo through i (inclusive) are less than or equal to the pivot, and the elements i+1 through j-1 (inclusive) are greater than the pivot. As this scheme is more compact and easy to understand, it is frequently used in introductory material, although it is less efficient than Hoare's original scheme. This scheme degrades to O(n²) when the array is already in order.^[10] There have been various variants proposed to boost performance including various ways to select pivot, deal with equal elements, use other sorting algorithms such as Insertion sort for small arrays and so on. In pseudocode, a quicksort that sorts elements lo through hi (inclusive) of an array A can be expressed as:

algorithm quicksort(A, lo, hi) is
    if lo < hi then
        p := partition(A, lo, hi)
        quicksort(A, lo, p - 1)
        quicksort(A, p + 1, hi)

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

Sorting the entire array is accomplished by quicksort(A, 0, length(A) - 1).

Consequences of Lomuto's algorithm

When all the elements of the array are same, then Lomuto's algorithm will result in n² comparisons and hence, the complexity of quick sort will become O(n²)