Quicksort

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

It has a time complexity of $\Omega (n\log n)$ and $O(n^2)$.

To generalise, we have two steps:

1. Partition: function takes in some array, a low and high position, then returns the index of the pivot.
2. Do the sorting.

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;
	*a = 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(list, low, pivot - 1); // for left sub-array
		quickSort(list, pivot + 1, high); // for right sub-array
	} // i.e. base case is to do nothing
}