Hello, learner! Today, we're delving into quick sort, a swift sorting algorithm akin to sorting toys by size. We'll explore how it works and implement it in TypeScript, so hang tight!

Quick sort, devised by Tony Hoare in 1959, leverages the divide-and-conquer strategy. It selects a pivot element and then arranges all smaller elements to one side and larger ones to the other.

Quick sort operates in three steps:

1. Selecting a pivot.
2. Shifting elements smaller than the pivot to one side and moving elements larger than the pivot to the other side.
3. Repeating these steps for both sides separately.

Consider, for instance, sorting [3, 9, 4, 7, 5, 1, 6, 2, 8] with 7 as the pivot. After one round, it becomes [3, 4, 5, 1, 6, 2, 7, 9, 8]. The pivot 7 is correctly placed, and we can then divide the array into two parts: [3, 4, 5, 1, 6] and [9, 8], which can be sorted separately.

Let's implement quick sort in TypeScript. First, we partition the array around the pivot in our partition function:

TypeScript
Copy to clipboard
1function partition(arr: number[], low: number, high: number): number {
2    let pivot: number = arr[high];  // The pivot is the last element
3    let i: number = low - 1;
4    for (let j: number = low; j < high; j++) {
5        if (arr[j] <= pivot) {   // If the current element is smaller than the pivot
6            i++;
7            [arr[i], arr[j]] = [arr[j], arr[i]];  // Swap the current element with the element at index i
8        }
9    }
10    [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]]; // Position the pivot in the correct position in the array
11    return i + 1;
12}

In this portion of the code, we select the last element as the pivot and place smaller elements on the left.

The function starts by initializing i to one index before the low. This i basically keeps track of the latest position where an element has been swapped because it was less than or equal to the pivot. If arr[j] is less than or equal to the pivot, i is incremented, and then arr[j] is swapped with arr[i]. Essentially, smaller elements get pushed towards the front of the array (or the given part of the array).

The low and high parameters control which part of the given array is under the partition operation. Using these parameters, we can apply the partition to some part of the array, which will be helpful later.

Then, we apply quick sort with a function that invokes partition and recursively sorts the two halves:

TypeScript
Copy to clipboard
1function quickSort(arr: number[], low: number, high: number): void {
2    if (low < high) {
3        let pi: number = partition(arr, low, high);
4        quickSort(arr, low, pi - 1);  // Recursively sort the left half
5        quickSort(arr, pi + 1, high);  // Recursively sort the right half
6    }
7}

Spot on! We've just created a fully functioning quick sort algorithm in TypeScript.

The time complexity of quick sort can vary. Generally speaking, the more unique items there are, the quicker quick sort works. In the best and average cases, it shines with a time complexity of $O(n \log n)$. However, the time complexity can degrade to $O(n^2)$ in the worst case.

Kudos! You've mastered the basics of quick sort and its implementation in TypeScript and have analyzed its time complexity. Up next, we have engaging practice exercises lined up. Are you ready to flex your newly acquired skills?