Quickselect — Expected Linear K-th

Partition around pivot; recurse into one side like binary search on rank.

Try this in Python

import random

def quickselect(a, k):
    pivot = random.choice(a)
    lows = [x for x in a if x < pivot]
    highs = [x for x in a if x > pivot]
    mids = [x for x in a if x == pivot]
    if k < len(lows):
        return quickselect(lows, k)
    if k < len(lows) + len(mids):
        return pivot
    return quickselect(highs, k - len(lows) - len(mids))

print(quickselect([9, 8, 7, 6, 5, 4], 2))

Key takeaways

• Worst case O(n^2) on bad pivots—median-of-medians fixes theory.
• heapq.nsmallest is fine for small k productively.
• Duplicates need three-way partition for efficiency.