# Quickselect

# Quickselect

Quickselect finds the k-th smallest element in an unsorted array. It uses the same partition idea as Quicksort but only recurses into one side, which reduces work.

You use it when you need a single order statistic such as median, top-k, or percentile, without fully sorting the array.

## Problem

Given an array $A$ of length $n$ and an integer $k$ with $0 \le k < n$, find a value $v$ such that

$$
v = \text{k-th smallest element of } A
$$

## Algorithm

Choose a pivot, partition the array into elements less than pivot and greater than pivot, then recurse only into the side that contains the k-th element.

```id="qs1"
quickselect(A, k):
    if length(A) == 1:
        return A[0]

    pivot = choose_pivot(A)

    L = [x in A where x < pivot]
    E = [x in A where x == pivot]
    R = [x in A where x > pivot]

    if k < length(L):
        return quickselect(L, k)
    else if k < length(L) + length(E):
        return pivot
    else:
        return quickselect(R, k - length(L) - length(E))
```

In practice, this is implemented in-place using partition indices.

## Example

Let

$$
A = [7, 2, 9, 4, 3]
$$

Find the element with $k = 2$ (0-based), which means the 3rd smallest.

Sorted order would be:

$$
[2, 3, 4, 7, 9]
$$

So the answer is:

$$
4
$$

Quickselect avoids full sorting and isolates the region containing the answer.

## Correctness

Partition guarantees that all elements in the left part are smaller than pivot, and all in the right part are larger. Therefore, the rank of the pivot is known after partition. The recursion preserves the invariant that the k-th element lies in the chosen subarray.

## Complexity

| case    | time     |
| ------- | -------- |
| best    | $O(n)$   |
| average | $O(n)$   |
| worst   | $O(n^2)$ |

Worst case occurs when pivot selection is consistently poor. Randomization avoids this in practice.

Space complexity:

$$
O(1)
$$

for in-place version.

## When to Use

Use Quickselect when:

* you need median or k-th element
* you do not need full sorting
* input fits in memory
* average case performance is sufficient

For guaranteed linear time, use Median of Medians, but with higher constant cost.

## Implementation

```id="qs2"
def quickselect(a, k):
    def partition(left, right, pivot_index):
        pivot = a[pivot_index]
        a[pivot_index], a[right] = a[right], a[pivot_index]
        store = left
        for i in range(left, right):
            if a[i] < pivot:
                a[store], a[i] = a[i], a[store]
                store += 1
        a[right], a[store] = a[store], a[right]
        return store

    left, right = 0, len(a) - 1

    while True:
        if left == right:
            return a[left]

        pivot_index = (left + right) // 2
        pivot_index = partition(left, right, pivot_index)

        if k == pivot_index:
            return a[k]
        elif k < pivot_index:
            right = pivot_index - 1
        else:
            left = pivot_index + 1
```

```id="qs3"
func Quickselect(a []int, k int) int {
	left, right := 0, len(a)-1

	for {
		if left == right {
			return a[left]
		}

		pivotIndex := (left + right) / 2
		pivotIndex = partition(a, left, right, pivotIndex)

		if k == pivotIndex {
			return a[k]
		} else if k < pivotIndex {
			right = pivotIndex - 1
		} else {
			left = pivotIndex + 1
		}
	}
}

func partition(a []int, left, right, pivotIndex int) int {
	pivot := a[pivotIndex]
	a[pivotIndex], a[right] = a[right], a[pivotIndex]

	store := left
	for i := left; i < right; i++ {
		if a[i] < pivot {
			a[store], a[i] = a[i], a[store]
			store++
		}
	}
	a[right], a[store] = a[store], a[right]
	return store
}
```