Quickselect

Problem

Given an unsorted array and integer k, return the kth smallest element (1-indexed).

Approach

Lomuto partition scheme. Pick a pivot, partition the array so elements less than the pivot come before it. If the pivot lands at position k-1 we are done; otherwise recurse on the correct half. Randomized pivot for expected O(n).

When to Use

Selection without full sort — "kth smallest/largest", "median", "top K" when you don't need sorted output. O(n) average vs O(n log n) for full sort. See also: heaps/kth_largest for streaming.

Complexity

Time	O(n) average, O(n^2) worst case
Space	O(1) (in-place partitioning)

Implementation

SolutionTestsChallenge

quickselect

Quickselect — find the kth smallest element.

Problem

Given an unsorted array and integer k, return the kth smallest element (1-indexed).

Approach

Lomuto partition scheme. Pick a pivot, partition the array so elements less than the pivot come before it. If the pivot lands at position k-1 we are done; otherwise recurse on the correct half. Randomized pivot for expected O(n).

When to use

Selection without full sort — "kth smallest/largest", "median", "top K" when you don't need sorted output. O(n) average vs O(n log n) for full sort. See also: heaps/kth_largest for streaming.

Complexity

Time: O(n) average, O(n^2) worst case Space: O(1) (in-place partitioning)

quickselect

quickselect(nums: list[int], k: int) -> int

Return the k-th smallest element (1-indexed).

quickselect([3, 2, 1, 5, 6, 4], 2) 2 quickselect([7], 1) 7

Source code in src/algo/sorting/quickselect.py

def quickselect(nums: list[int], k: int) -> int:
    """Return the *k*-th smallest element (1-indexed).

    >>> quickselect([3, 2, 1, 5, 6, 4], 2)
    2
    >>> quickselect([7], 1)
    7
    """
    if k < 1 or k > len(nums):
        msg = f"k={k} out of range for length {len(nums)}"
        raise ValueError(msg)

    def _partition(lo: int, hi: int) -> int:
        # Randomized pivot to avoid worst case
        pivot_idx = random.randint(lo, hi)
        nums[pivot_idx], nums[hi] = nums[hi], nums[pivot_idx]
        pivot = nums[hi]
        store = lo
        for i in range(lo, hi):
            if nums[i] < pivot:
                nums[store], nums[i] = nums[i], nums[store]
                store += 1
        nums[store], nums[hi] = nums[hi], nums[store]
        return store

    lo, hi = 0, len(nums) - 1
    target = k - 1

    while lo <= hi:
        pivot_pos = _partition(lo, hi)
        if pivot_pos == target:
            return nums[pivot_pos]
        if pivot_pos < target:
            lo = pivot_pos + 1
        else:
            hi = pivot_pos - 1

    # Should not reach here if k is valid
    msg = "quickselect failed"
    raise RuntimeError(msg)

tests/sorting/test_quickselect.py

"""Tests for quickselect."""

import pytest
from hypothesis import given
from hypothesis import strategies as st

from algo.sorting.quickselect import quickselect


class TestQuickselect:
    def test_basic(self) -> None:
        assert quickselect([3, 2, 1, 5, 6, 4], 2) == 2

    def test_single_element(self) -> None:
        assert quickselect([7], 1) == 7

    def test_kth_largest_equivalent(self) -> None:
        nums = [3, 2, 3, 1, 2, 4, 5, 5, 6]
        # 4th smallest = 3
        assert quickselect(list(nums), 4) == 3

    def test_k_equals_length(self) -> None:
        assert quickselect([5, 3, 1, 2, 4], 5) == 5

    def test_k_out_of_range_raises(self) -> None:
        with pytest.raises(ValueError):
            quickselect([1, 2], 3)

    def test_k_zero_raises(self) -> None:
        with pytest.raises(ValueError):
            quickselect([1, 2], 0)

    @given(
        data=st.lists(
            st.integers(min_value=-100, max_value=100), min_size=1, max_size=50
        ),
    )
    def test_matches_sorted(self, data: list[int]) -> None:
        k = 1
        assert quickselect(list(data), k) == sorted(data)[k - 1]

Implement it yourself

Run: just challenge sorting quickselect

Then implement the functions to make all tests pass. Use just study sorting for watch mode.

Reveal Solution

quickselect

Quickselect — find the kth smallest element.

Problem

Given an unsorted array and integer k, return the kth smallest element (1-indexed).

Approach

Lomuto partition scheme. Pick a pivot, partition the array so elements less than the pivot come before it. If the pivot lands at position k-1 we are done; otherwise recurse on the correct half. Randomized pivot for expected O(n).

When to use

Selection without full sort — "kth smallest/largest", "median", "top K" when you don't need sorted output. O(n) average vs O(n log n) for full sort. See also: heaps/kth_largest for streaming.

Complexity

Time: O(n) average, O(n^2) worst case Space: O(1) (in-place partitioning)

quickselect

quickselect(nums: list[int], k: int) -> int

Return the k-th smallest element (1-indexed).

quickselect([3, 2, 1, 5, 6, 4], 2) 2 quickselect([7], 1) 7

Source code in src/algo/sorting/quickselect.py

def quickselect(nums: list[int], k: int) -> int:
    """Return the *k*-th smallest element (1-indexed).

    >>> quickselect([3, 2, 1, 5, 6, 4], 2)
    2
    >>> quickselect([7], 1)
    7
    """
    if k < 1 or k > len(nums):
        msg = f"k={k} out of range for length {len(nums)}"
        raise ValueError(msg)

    def _partition(lo: int, hi: int) -> int:
        # Randomized pivot to avoid worst case
        pivot_idx = random.randint(lo, hi)
        nums[pivot_idx], nums[hi] = nums[hi], nums[pivot_idx]
        pivot = nums[hi]
        store = lo
        for i in range(lo, hi):
            if nums[i] < pivot:
                nums[store], nums[i] = nums[i], nums[store]
                store += 1
        nums[store], nums[hi] = nums[hi], nums[store]
        return store

    lo, hi = 0, len(nums) - 1
    target = k - 1

    while lo <= hi:
        pivot_pos = _partition(lo, hi)
        if pivot_pos == target:
            return nums[pivot_pos]
        if pivot_pos < target:
            lo = pivot_pos + 1
        else:
            hi = pivot_pos - 1

    # Should not reach here if k is valid
    msg = "quickselect failed"
    raise RuntimeError(msg)