Quicksort

Quicksort is a fast sorting algorithm. It uses a divide-and-conquer approach — for an array $A$ and an index $x$, if all elements to the left of $x$ are less than $x$, and all elements to the right are greater than $x$, then we know A[x] is in the correct position. We call this index $x$ a pivot.

Quicksort has two steps:

1. Partition — we take some array, a low and high index, then return the index of the pivot.
2. Recursively partition and sort.

It has a time complexity of average-case $O(n\log n)$ and worst-case $O(n^2)$.

We can take the first element as the pivot. Then, we set some left and right indices of the array to sort within. We increment left by one index to look for arr[left] > pivot. We decrement right to look for arr[right] < pivot. We can then quicksort the left and right sub-arrays until one recursive layer of QS has low > high.

Here is a recursive implementation of quicksort in C:

int swap(int *a, int *b) {
	int temp = *a;
	*a = *b;
	*b = temp;
}
 
int partition(int list[], int low, int high) {
	bool done = false;
	int pivotInd = low, left = low, right = high;
	while (!done) {
		while (left <= right && list [pivotInd] > list[left]) {
			left++;
		}
		while (left <= right && list[pivotInd] < list[right]) {
			right--;
		}
		if (left > right) { 
		// partitioning ended, so we flip our bool variable from above
			swap(&list[right], &list[pivotInd]);
			done = true;
		} else {
			swap(&list[right], &list[left]);
		}
	}
	return pivotInd;
}
 
void quickSort (int arr[], int low, int high) {
	if (low > high) {
		int pivot = partition(arr, low, high);
		quickSort(arr, low, pivot - 1); // for left sub-array
		quickSort(arr, pivot + 1, high); // for right sub-array
	} // i.e. base case is to do nothing
}

Time complexity

The worst-case runtime is $\Theta (n^2)$, when the list is already sorted. The pivot we pick will always be the largest/smallest, and each partition, we get an empty array and one empty array of size $n-1$. One way we can avoid the worst-case runtime is to randomly select a pivot, instead of deterministically choosing the minimum or maximum index of the sub-array. In the case of a sorted list, this prevents the pivot from always being the largest/smallest.

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

The best-case runtime is $\Theta (n\log n)$, where the pivot is always the median:

$$T(n)=2T(n/2)+O(n)$$

The average/expected runtime is $\Theta (n\log n)$.

Proof

We can rigorously prove quicksort’s correctness with strong induction.

See also

• Mergesort