# Randomized Quickselect

# Randomized Quickselect

Randomized Quickselect improves Quickselect by choosing the pivot uniformly at random. This removes dependence on input order and avoids pathological worst cases in practice.

The structure remains identical to Quickselect. Only pivot selection changes.

## Problem

Given an array $A$ of length $n$ and an integer $k$ with $0 \le k < n$, return the k-th smallest element.

## Algorithm

At each step, select a random pivot, partition, and recurse into one side.

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

    pivot = random choice from 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 randomized_quickselect(L, k)
    else if k < length(L) + length(E):
        return pivot
    else:
        return randomized_quickselect(R, k - length(L) - length(E))
```

## Key Idea

Random pivot selection ensures that, in expectation, the partition splits the array reasonably well. This leads to linear expected time regardless of input distribution.

## Correctness

Partitioning preserves rank ordering. Randomization does not change correctness, only the distribution of recursion depth.

## Complexity

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

Worst case remains possible but has exponentially small probability.

Space:

$$
O(1)
$$

for in-place version.

## When to Use

Use Randomized Quickselect when:

* input may be adversarial or unknown
* you want stable performance across datasets
* average-case linear time is sufficient

It is the standard practical selection algorithm.

## Implementation

```id="rqs2"
import random

def randomized_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 = random.randint(left, right)
        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="rqs3"
import "math/rand"

func RandomizedQuickselect(a []int, k int) int {
	left, right := 0, len(a)-1

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

		pivotIndex := left + rand.Intn(right-left+1)
		pivotIndex = partition(a, left, right, pivotIndex)

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