> For the complete documentation index, see [llms.txt](https://kdongs.gitbook.io/kdocs/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://kdongs.gitbook.io/kdocs/sort/bubble-sort.md).

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

{% hint style="info" %}
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})$$*.*
{% endhint %}

#### Implementation on Arrays

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