Implement quickselect (k-th smallest, seeded pivot for determinism) and verify it against a full sort.

Answer

import random def quickselect(a, k): a = a[:] rng = random.Random(42) lo, hi = 0, len(a) - 1 target = k - 1 while lo < hi: p = rng.randint(lo, hi) a[p], a[hi] = a[hi], a[p] pivot = a[hi] i = lo for j in range(lo, hi): if a[j] < pivot: a[i], a[j] = a[j], a[i] i += 1 a[i], a[hi] = a[hi], a[i] if target == i: return a[i] elif target < i: hi = i - 1 else: lo = i + 1 return a[lo] data = [7, 10, 4, 3, 20, 15, 8, 1] for k in [1, 4, 8]: got = quickselect(data, k) want = sorted(data)[k - 1] print(f"k={k}: quickselect={got} sorted={want} match={got == want}")