Bubble Sort

About

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;
            }
        }
    }
}