Bubble Sort

Complexity: O(N^2)

Bubble sort is the simplest sorting algoritm, the way we sort the data is by comparing the current and next item of an array, if the current item is greater than the next item then we swap the position.

Suppose we have this data.

a = [1,3,2,7,4,5]

Then we loop to the data and compare it, let's say we on this first position we compare the current item with the next item. In this case we comparing 1 and 3 because 1 is not grater than 3 we not swaping it.

[1,3,2,7,4,5]
 ^ ^

The next iteration we are comparing the item 3 and 2 because the item 3 is greater and the next item which is 2 we need to swap it.

[1,3,2,7,4,5]
   ^ ^

So now the data is swapped and it will look like this.

[1,2,3,7,4,5]
   ^ ^ -> swapped!

And the process will go on until the end.

Let's implement it.

export default function bubble_sort(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]) {
        let cur = arr[j]
        arr[j] = arr[j+1]
        arr[j+1] = cur
      }
    }
  }
}