# Randomized Quicksort

# Randomized Quicksort

Randomized quicksort modifies quicksort by choosing the pivot at random. This removes dependence on input order and prevents consistently bad partitions.

The algorithm retains the same structure as quicksort but replaces deterministic pivot selection with a random choice.

## Problem

Given an array $A$ of length $n$, reorder it such that:

$$
A[0] \le A[1] \le \dots \le A[n-1]
$$

## Idea

Instead of always choosing a fixed pivot position, pick a random index between $lo$ and $hi$, then swap it with the last element and use it as the pivot.

This makes every permutation equally likely, so worst case behavior becomes extremely unlikely.

## Algorithm

```text id="s2x9kf"
randomized_quicksort(A, lo, hi):
    if lo >= hi:
        return

    p = randomized_partition(A, lo, hi)

    randomized_quicksort(A, lo, p - 1)
    randomized_quicksort(A, p + 1, hi)
```

```text id="c7m4qp"
randomized_partition(A, lo, hi):
    r = random integer in [lo, hi]
    swap A[r] and A[hi]

    return partition(A, lo, hi)
```

The partition step is the same as standard quicksort.

## Example

Let:

$$
A = [4, 2, 7, 1, 5]
$$

Suppose a random pivot index selects value $2$.

Swap with last element:

$$
[4, 5, 7, 1, 2]
$$

Partition around $2$:

$$
[1, 2, 7, 4, 5]
$$

Then recursively sort left and right parts.

## Correctness

Randomization changes only pivot selection. The partition step still ensures that the pivot is placed between smaller and larger elements. The recursive structure remains valid, so correctness follows from standard quicksort.

## Complexity

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

The worst case remains possible but occurs with very low probability.

Expected recurrence:

$$
T(n) = T(k) + T(n-k-1) + O(n)
$$

where $k$ is random.

## Properties

| property             | value  |
| -------------------- | ------ |
| stable               | no     |
| in-place             | yes    |
| randomized           | yes    |
| expected performance | strong |

## Notes

Randomization protects quicksort from adversarial inputs. It is widely used in practice because it is simple and effective.

In many implementations, a pseudo random generator is used, which is sufficient for performance purposes.

## Implementation

```python id="m4t2qs"
import random

def randomized_quicksort(a):
    def sort(lo, hi):
        if lo >= hi:
            return

        p = partition(lo, hi)
        sort(lo, p - 1)
        sort(p + 1, hi)

    def partition(lo, hi):
        r = random.randint(lo, hi)
        a[r], a[hi] = a[hi], a[r]

        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

    sort(0, len(a) - 1)
    return a
```

```go id="x9d3pf"
import "math/rand"

func RandomizedQuickSort(a []int) {
	var sort func(int, int)

	sort = func(lo, hi int) {
		if lo >= hi {
			return
		}

		p := randomizedPartition(a, lo, hi)
		sort(lo, p-1)
		sort(p+1, hi)
	}

	sort(0, len(a)-1)
}

func randomizedPartition(a []int, lo, hi int) int {
	r := lo + rand.Intn(hi-lo+1)
	a[r], a[hi] = a[hi], a[r]

	pivot := a[hi]
	i := lo

	for j := lo; j < hi; j++ {
		if a[j] <= pivot {
			a[i], a[j] = a[j], a[i]
			i++
		}
	}

	a[i], a[hi] = a[hi], a[i]
	return i
}
```