QuickSelect

Problem: Find $k$-th smallest without fully sorting.

Approach: Partition like quicksort, recurse only one side.

function quickSelect(arr, left, right, k):
    if left == right: return arr[left]
    pivotIdx = partition(arr, left, right)
    if k == pivotIdx: return arr[k]
    else if k < pivotIdx:
        return quickSelect(arr, left, pivotIdx - 1, k)
    else:
        return quickSelect(arr, pivotIdx + 1, right, k)

Expected: $O(n)$. Worst: $O(n^2)$. Use median-of-medians for $O(n)$ guaranteed.