Quick Sort

We saw with merge sort that we can sort an array in \(O(n \log n)\) time. However, merge sort requires \(O(n)\) extra space. Quick sort is another comparison based sorting algorithm that takes some ideas from merge sort and improves upon it, such as not requiring extra space.

In the merge sort algorithm we always divided the array into two halves and then sorted the two halves. Quick sort has a similar approach, but rather then just splitting the array down the middle, we create two subarrays in a different way to recursively sort the array. For the quick sort algorithm we do the following:

1. We pick an element as a so called pivot. There are many ways to pick a pivot, but for now we will just pick the last element in the array.
2. We then find the correct position for the pivot element in the array and swap it with the element currently at that position.
3. We then create the two partitions to be further recursively sorted to the left and right of the pivot element. The key to the quick sort algorithm is this partitioning step. When partitioning we rearrange the elements in the array in such a way that all elements to the left of the pivot are less than the pivot and all elements to the right of the pivot are greater or equal to the pivot.
4. We then recursively sort the two partitions by repeating the above steps.

public void quickSort(int[] arr) {
    quickSort(arr, 0, arr.length - 1);
}
 
private void quickSort(int[] arr, int low, int high) {
    if (low < high) {
        int pivotIndex = partition(arr, low, high);
        quickSort(arr, low, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, high);
    }
}
 
private int partition(int[] arr, int low, int high) {
    int pivot = arr[high]; // pick the last element as the pivot
    int i = low - 1;
    // move all elements less than the pivot to the left of the pivot
    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(arr, i, j);
        }
    }
    swap(arr, i + 1, high);
    return i + 1;
}
 
private void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

Correctness

The correctness comes from the fact that in the partitioning step we always put the pivot element in the correct position. Because we also always put all elements less than the pivot to the left of the pivot and all elements greater or equal to the pivot to the right of the pivot, we can guarantee that the correct place for the next pivots we choose for the two partitions will also be in the correct place. Therefore, eventually all elements will be in the correct place and the array will be sorted.

Analysis

We can see that in the best case scenario the recurrence relation slightly changes and becomes:

Randomized Quick Sort

The way we pick the pivot element in the quick sort algorithm can have a big impact on the performance of the algorithm. If we have the worst case scenario where we always pick the smallest or largest element as the pivot and the array is already sorted, the quick sort algorithm will have a time complexity of \(O(n^2)\). If we have the best case scenario where we always pick the median element as the pivot, the quick sort algorithm will have a time complexity of \(O(n \log n)\).

To avoid the worst case scenario we can pick the pivot element at random. This makes it highly unlikely that we will always pick the smallest or largest element as the pivot.

This results in a time complexity of \(O(n \log n)\) on average.

I don’t yet know how to prove this tho, so I will leave it at that for now.

Median of Medians

ideally we would like to pick the median element as the pivot. This way we can guarantee that the two partitions are of equal size. However, finding the median element in an array quickly is not trivial.