Bubble sort

sorting algorithms

• move largest number to end
  • move second largest to second last
    • ...continue
• Gauss: sum of numbers in range (1..=n) is n(n+1)/2

• O(n^2)

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