Sort

Sorting (Bubble, Selection, Insertion, Merge, Quick, Counting, Radix) - VisuAlgo

Bubble Sort

The simplest sorting algorithm, it's a Greedy algorithm. Basically starts at first DS position and checks if it is greater than the next one, and keeps repeating this process until it is done.

Asymptotically this will be $O(N²)$, since in the worst case you will go through the $N$ size DS $N$ times.

In practice, after each run the last element on the DS will always be the largest, so you don't have to go $N*N$, you end up going $N \rightarrow N-1 \rightarrow N-2 \rightarrow ... \rightarrow 1$ and having $O(\frac{N(N+1)}{2})$.

Implementation on Arrays

function bubbleSort(arr: number[]): void {
    for (let i = 0; i < arr.length; i++) {
        for (let j = 0; j < (arr.length - 1 - i); j++ ) {
            if (arr[j] > arr[j + 1]) {
                const tmp = arr[j];
                arr[j] = arr[j + 1];
                arr[j+1] = tmp;
            }
        }
    }
}

Selection Sort

Insertion Sort

Merge Sort

Quick Sort

It's a Divide and Conquer algorithm. It takes a pivot value that usually is in the middle of the DS, and sorts every value smaller or equal than the pivot to it's left and every value greater to the right.

After this, you take a new pivot for each of the new sections, and do it again, and on and on... until reaching the base case of a section of size 0 or 1.

It should do the sorting inplace, instead of creating temporary structures to hold these middle arrays.

Asymptotically QuickSort can be $O(N\ log N)$ or $O(N²)$ depending on how you pick your pivots.

The literal wort case scenario would be having a reverse ordered Array and picking the last element as the pivot.

Implementation on Arrays

recursive

function partition(arr: number[], lo: number, hi: number): number {
    const pivot = Math.floor((lo + hi) / 2);
    let idx = lo - 1;
    
    for (let i = lo; i < hi; i++) {
        if (arr[i] <= arr[pivot]) {
            idx++;
            const temp = arr[i];
            arr[i] = arr[idx];
            arr[idx] = temp;
        }
    }
    
    idx++;
    arr[hi] = arr[idx];
    arr[idx] = arr[pivot];
    
    return idx;
}

function quickSort(arr: number[], lo: number, hi: number): void {
    if (lo >= hi) return;
    const pivotIdx = partition(arr, lo, hi);
    
    quickSort(arr, lo, pivotIdx - 1);
    quickSort(arr, pivotIdx + 1, hi);
}

quickSort(arr, 0, arr.length - 1);

Radix Sort

Heap Sort