# Quicksort

# Quicksort

Quicksort is a divide and conquer sorting algorithm. It chooses a pivot value, partitions the array so that smaller elements go before the pivot and larger elements go after it, then recursively sorts both sides.

It is one of the most important practical sorting algorithms because it is fast in memory, has good cache behavior, and usually needs only logarithmic stack space. Its main weakness is that bad pivot choices can produce quadratic time.

## Problem

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

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

## Idea

Choose a pivot $p$. Rearrange the array into three logical parts:

$$
\text{values } \le p,\quad p,\quad \text{values } \ge p
$$

After partitioning, the pivot is in its final sorted position. The left and right parts can then be sorted independently.

## Algorithm

```text id="e7x2qa"
quicksort(A, lo, hi):
    if lo >= hi:
        return

    p = partition(A, lo, hi)

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

One simple partition scheme is Lomuto partition.

```text id="k6sx1p"
partition(A, lo, hi):
    pivot = A[hi]
    i = lo

    for j from lo to hi - 1:
        if A[j] <= pivot:
            swap A[i] and A[j]
            i += 1

    swap A[i] and A[hi]
    return i
```

## Example

Let:

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

Choose pivot $5$.

Partition:

| value | action     |
| ----- | ---------- |
| 4     | move left  |
| 2     | move left  |
| 7     | stay right |
| 1     | move left  |

After partition:

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

The pivot $5$ is now fixed. Recursively sort:

$$
[4, 2, 1]
$$

and

$$
[7]
$$

Final result:

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

## Correctness

Partition places the pivot into a position where every element on its left is less than or equal to the pivot and every element on its right is greater than or equal to the pivot. The pivot therefore has its final sorted position.

The recursive calls sort the left and right subarrays. Since all left elements are no larger than the pivot and all right elements are no smaller than the pivot, combining the sorted left side, the pivot, and the sorted right side gives a sorted array.

## Complexity

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

The worst case occurs when partitions are extremely unbalanced, for example when the pivot is repeatedly the smallest or largest element.

Space usage comes from recursion:

| case               | space       |
| ------------------ | ----------- |
| balanced recursion | $O(\log n)$ |
| worst recursion    | $O(n)$      |

## Properties

| property         | value |
| ---------------- | ----- |
| stable           | no    |
| in-place         | yes   |
| comparison based | yes   |
| adaptive         | no    |
| cache behavior   | good  |

## Notes

Quicksort is fast in practice, but raw quicksort should be protected against bad pivots. Common improvements include randomized pivots, median of three selection, three way partitioning for duplicate heavy arrays, and introsort fallback to heapsort.

## Implementation

```python id="j2z7fe"
def 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):
        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="2y9sqa"
func QuickSort(a []int) {
	var sort func(int, int)

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

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

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

func partition(a []int, lo, hi int) int {
	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
}
```