Quickselect

Partition the array around a pivot. The pivot ends at index p, which is its final sorted position. If p == k - 1, the pivot is the answer. If p < k - 1, the answer lies to the right, so continue on [p+1..hi]. Otherwise it lies to the left.

Quick sort recurses on both sides; quickselect recurses on one. In the animation the discarded part of the array fades out, and you can change k to see it follow a different path. It is the fastest option when the whole array is in memory and you can reorder it.

1public static int quickSelect(int[] arr, int k) {            // k-th smallest, 1-based
2    int lo = 0, hi = arr.length - 1, idx = k - 1;
3    while (lo <= hi) {
4        int p = partition(arr, lo, hi);
5        if (p == idx) return arr[p];
6        if (p < idx) lo = p + 1;
7        else hi = p - 1;
8    }
9    throw new IllegalArgumentException("k out of range");
10}

1public static int quickSelect(int[] arr, int k) {        // k-th smallest, 1-based
2    int lo = 0, hi = arr.length - 1, idx = k - 1;
3    while (lo <= hi) {
4        int p = partition(arr, lo, hi);                  // Lomuto, pivot = arr[hi]
5        if (p == idx) return arr[p];
6        if (p < idx) lo = p + 1;                         // answer is on the right
7        else hi = p - 1;                                 // answer is on the left
8    }
9    return -1;
10}

With a fixed pivot rule, an adversarial input (such as sorted data and a last-element pivot) forces bad splits. Picking the pivot at random makes the running time independent of the input order.

Swap a randomly chosen element to the end before partitioning. Median-of-three is a cheaper heuristic that works well on sorted and reverse sorted data but is not random.

1int r = lo + ThreadLocalRandom.current().nextInt(hi - lo + 1);
2swap(arr, r, hi);                       // move the random pivot to the end
3int p = partition(arr, lo, hi);

Call a pivot good if it lands in the middle half of the sorted order (between the 25th and 75th percentile). That happens with probability 1/2. After a good pivot, at most 3/4 of the elements remain. In expectation two partitions are needed to get one good one.

So the expected work is E[T(n)] ≤ 2n + E[T(3n/4)]. Unrolling gives 2n · (1 + 3/4 + (3/4)² + …) = 2n / (1 - 3/4) = 8n = O(n). The partitioning cost shrinks geometrically, unlike quick sort, where both sides stay.

If every pivot is the minimum or the maximum, each round removes only one element, giving n + (n - 1) + … + 1 = O(n²). With a random pivot this has vanishingly small probability. With a fixed pivot rule it is easy to trigger.

Introselect protects against this: it counts rounds and switches to the median-of-medians algorithm (next lesson) when progress is too slow, so the worst case becomes O(n). C++ std::nth_element does this.

Lomuto partitioning puts values equal to the pivot on the right side. When all elements are equal, every partition removes only one element and the algorithm is quadratic. Run the “All equal (quadratic)” preset to see it.

Use three-way partitioning (< pivot, = pivot, > pivot). If the target index falls inside the equal band, the answer is the pivot value and the search ends immediately. Otherwise continue on the strictly smaller or strictly larger part.

1// three-way quickselect step: [lo..lt-1] < pivot, [lt..gt] == pivot, [gt+1..hi] > pivot
2if (idx < lt) hi = lt - 1;
3else if (idx > gt) lo = gt + 1;
4else return pivot;                      // idx is inside the equal band: done