QuickSort

Quick Sort is a slightly faster sorting algorithm compared to Merge Sort or Heap Sort for randomized data. In the worst case the performance can be O(N²), but generally it's a decent O(logN).

It's implemented with two functions:

partition

calculates the pivot, and swaps the values around the pivot point

quick_sort

calls partition, and calls itself, AKA recursion bookkeeping

Typescript

export default function quick_sort(arr: number[]): void {
    qs(arr, 0, arr.length - 1)
}

function qs(arr: number[], lo: number, hi: number): void {
    // base
    if (lo >= hi) {
        return
    }

    const pivotIdx = partition(arr, lo, hi)
    qs(arr, lo, pivotIdx - 1)
    qs(arr, pivotIdx + 1, hi)
}

function partition(arr: number[], lo: number, hi: number): number {
    const pivot = arr[hi]

    let idx = lo - 1 // this idx starts at the point, before the index you want to sort
    for (let i = lo; i < hi; ++i) {
        if (arr[i] <= pivot) {
            // swap if a value was lower than the pivot value
            idx++
            const tmp = arr[i]
            arr[i] = arr[idx]
            arr[idx] = tmp
        }
    }
    // swap the pivot value itself
    idx++
    arr[hi] = arr[idx]
    arr[idx] = pivot

    return idx
}

References

• FE: Last Algorithm Course You'll Need