Sometimes you need only the k-th smallest element (indices start at 0): the minimum, the median, the 90th percentile. Sorting the whole array in O(n log n) is excessive. Quickselect uses the same partition as quicksort, but after each partition continues with one side only, and finds the answer in O(n) on average. It is a divide-and-conquer idea, see divide and conquer.

Partition around the pivot, then keep one side
Partition around the pivot, then keep one side

Lomuto partition

The pivot is the last element. The loop moves the elements smaller than the pivot to the front, i is the border of that zone. Finally the pivot is swapped to position i: that is its final place in the sorted array.

python
def partition(a, lo, hi):
    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]
    return i

a = [7, 2, 9, 4, 3, 8, 5]
p = partition(a, 0, len(a) - 1)
print(a)
print("pivot index:", p)
text
[2, 4, 3, 5, 9, 8, 7]
pivot index: 3

Quickselect