Quicksort, Partitioning and Pivot Choices

This lesson uses the final element as pivot and a Lomuto-style partition. A boundary marks the next place for an item no greater than the pivot. Scan all other items; when one qualifies, swap it to the boundary and advance the boundary. Finally swap the pivot into the boundary position.

For [6,2,7,2,5], pivot 5 ends at index 2 and the array after this partition is [2,2,5,6,7]. The left and right partitions need not themselves be sorted in a general case. Other valid quicksort variants use different pivots, comparisons or two-ended scans, so their intermediate states can differ while implementing the same overall sorting task.

Once the pivot is placed, sort positions low through pivot_index−1 and pivot_index+1 through high. The pivot is excluded from both recursive calls. A subproblem with fewer than two items needs no partition. These shrinking bounds establish termination for finite inputs, including when the pivot ends at an extreme.

The implementation modifies the original list. Partitioning takes linear time in the size of the subproblem. Balanced partitions give approximately log₂n levels with linear total work per level, yielding O(n log n) time. A repeatedly extreme pivot can leave subproblems of sizes n−1, n−2 and so on, giving quadratic worst-case time.

Choosing the last item performs poorly on some already ordered inputs, and this <= partition rule can also create unbalanced splits for many equal values. Randomising or improving pivot selection can reduce common bad patterns but does not turn every possible input into a guaranteed balanced partition. Do not describe quicksort’s average-case bound as an unconditional worst-case guarantee.

This in-place partition uses constant extra data space, but recursion uses a stack: typically logarithmic for balanced splits and potentially linear for this straightforward worst case. The swaps do not preserve the original order of equal keys, so this variant is not stable. Test duplicates, empty lists and sorted/reversed order as well as a mixed example.

def quicksort(values):
    def partition(low, high):
        pivot = values[high]
        boundary = low
        for scan in range(low, high):
            if values[scan] <= pivot:
                values[boundary], values[scan] = values[scan], values[boundary]
                boundary += 1
        values[boundary], values[high] = values[high], values[boundary]
        return boundary

    def sort(low, high):
        if low < high:
            pivot_index = partition(low, high)
            sort(low, pivot_index - 1)
            sort(pivot_index + 1, high)

    sort(0, len(values) - 1)
    return values

print(quicksort([6, 2, 7, 2, 5]))

Attempt the task before opening its worked response. Record each change of state, explain the rule used, and check the result against the original requirements. Code examples labelled Python 3 use that language’s conventions; pseudocode states its own assumptions.