Quick Select

Quick select often comes up when the question asks for the first/last K elements or the Kth largest/smallest element

Runtime

$$T(n) = T(\frac{n}{2}) + O(n)$$

• Best/Average: $O(n)$ can guaranteed by shuffling the array

• Worst: $O(n^2)$if sorted

Techniques

Kth Element

Arrange largest elements in front by inverting the pivot comparison. This is a common problem type that tests if you know exactly how the partitioning algorithm works.

Partitioning Algorithms

Pick a pivot, partition elements smaller than the pivot to the left, and elements larger to the right of the pivot

Lomuto

idx-1 is the pivot index after performing the partitioning the array. Think of idx as the position for the next element that is smaller than the pivot value

• Easier to implement

def select(start, end):
    # Randomly choose a pivot value to guarantee O(n)
    random = randint(start, end)
    # Swap the pivot value to the end
    points[end], points[random] = points[random], points[end]
    # Calculate the value of the pivot
    pivot_value = calculate(points[end])
    idx = start
    for i in range(start, end + 1):
        # If current value less than pivot, then swap to idx position
        if calculate(points[i]) <= pivot_value:
            points[i], points[idx] = points[idx], points[i]
            idx += 1
    return idx - 1

s, e, pos = 0, len(points) - 1, len(points)
while pos != k:
    pos = select(s, e)
    if pos < k:
        s = pos + 1
    else:
        e = pos - 1
return points[:k]

Hoare

Choose first element as pivot

• Faster in theory

Two pointers, find 2 elements where arr[left] > pivot and arr[right] < pivot, swap and continue. When pointers converge, they converge at where the pivot should be so swap arr[start] and arr[left].

partition(start, end):
    i, j = start, end + 1
    while True:
        while i < end and arr[i] < arr[start]:
            i += 1
        while j > start and arr[i] > arr[start]:
            j -= 1
        if i >= j:
            break
        swap(arr[i], arr[j])
        swap(arr[start], arr[j])
    return j