The Quick Sort Algorithm
Tags: programming, tutorial, typescript, learning
Published: 2024-03-12 22:47:39

## 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:

```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:

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

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

```typescript
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:

```typescript
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:

```typescript
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);
}
```