The Quick Sort Algorithm

Intro

I recently took a data structures and algorithms course as part of my pursuit to learn lower level programming and computer science concepts. As the saying goes, the best way of solidifying your knowledge in something is to teach it, and since I've already filled my quota for boring my partner with coding talk for the month (probably the year), I thought I'd write a series of posts with some of the things I've learned. This is one such post.

What is the Quick Sort Algorithm?

The Quick Sort algorithm is another example of a 'divide and conquer' algorithm that takes an un-sorted array and, you guessed it, sorts it! It works by selecting a pivot (usually the last element in the array) and then adding the remaining elements in the array to 2 sub-arrays - 1 that will contain all the elements smaller than the pivot, and the other that will contain the elements greater than, or equal to, the pivot. We then recurse this step on the sub arrays until the entire array is sorted. This algorithm has an average time complexity of O(nlogn) but its worst case is O(n^2) when the array is already sorted but in reverse order.

How does it work

To explain how it works, here's some pseudo-code:

pivot = arr.length -1
smallerItems = []
largerItems = []

for element in array to sort:
    if element < pivot
        add to smallerItems
    else
        add to largerItems

sort(smallerItems)
sort(largerItems)

How do we implement it

Here's a heavily commented implementation in Typescript:

function quickSort(arr: number[]): number[] {
    // base case
    if (arr.length <= 1) {
        return arr;
    }

    // select our pivot -- the last element in the array
    const pivot = arr[arr.length - 1];

    // create 2 sub-arrays
    const leftArr: number[] = [];
    const rightArr: number[] = [];

    // loop through the array
    for (let i = 0; i < arr.length - 1; i++) {
        // if the current item is less than the value of our pivot
        // add the item to our leftArr, otherwise, add it to our
        // rightArr
        if (arr[i] < pivot) {
            leftArr.push(arr[i]);
        } else {
            rightArr.push(arr[i]);
        }
    }

    // repeat/recurse this process for our sub arrays
    return [...quickSort(leftArr), pivot, ...quickSort(rightArr)];
}

An alternative implementation

Whilst the above implementation works, it would be pretty costly when it comes to memory as the input array scales. An alternative way of writing this function, is to split it up into 3 parts and sort our array inline without the need to create any additional arrays. Let's see what this looks like...

First, let's define our interface:

function quickSort(arr: number[]): void {}

Next, we'll create a function that gets our pivot index and handles our recursion.

function sort(arr: number[], lo: number, hi: number): void {
    if (lo >= hi) {
        return;
    }

    const pivotIndex = partition(arr, lo, hi);
    sort(arr, lo, pivotIndex - 1);
    sort(arr, pivotIndex + 1, hi);
}

function quickSort(arr: number[]): void {
    sort(arr, 0, arr.length - 1);
}

Finally, we'll create our third function which manages 3 pointers - our pivot, our index (which starts at -1), and the item we're currently checking (current). Current walks through the array, and if the item is less than or equal to our pivot, we increment the index and swap the items located at index and current. At the end of our iteration, we increment our index and swap the items at our index and pivot, then we return the index. Here's what that function looks like:

function partition(arr: number[], lo: number, hi: number): number {
    // set our pivot to the end of the array
    const pivot = arr[hi];

    // set out index to the start of the array -1
    let idx = lo - 1;

    // loop through our array
    for (let i = lo; i < hi; ++i) {
        // if the item is less than or equal to the pivot
        // increment the index, then swap it with the item
        // at the index
        if (arr[i] <= pivot) {
            idx++;
            [arr[i], arr[idx]] = [arr[idx], arr[i]];
        }
    }

    // after we've finished walking the array,
    // increment the index, then swap the item
    // at the pivot with the item at the index
    idx++;
    [arr[hi], arr[idx]] = [arr[idx], arr[hi]];

    // return the index
    return idx;
}

Ok, now let's put it all together:

function partition(arr: number[], lo: number, hi: number): number {
    const pivot = arr[hi];
    let idx = lo - 1;

    for (let i = lo; i < hi; ++i) {
        if (arr[i] <= pivot) {
            idx++;
            [arr[i], arr[idx]] = [arr[idx], arr[i]];
        }
    }
    idx++;
    [arr[hi], arr[idx]] = [arr[idx], arr[hi]];

    return idx;
}

function sort(arr: number[], lo: number, hi: number): void {
    if (lo >= hi) {
        return;
    }

    const pivotIndex = partition(arr, lo, hi);
    sort(arr, lo, pivotIndex - 1);
    sort(arr, pivotIndex + 1, hi);
}

function quickSort(arr: number[]): void {
    sort(arr, 0, arr.length - 1);
}