[JS] 버블 정렬

배열의 인접한 두 요소를 비교해가며 정렬하는 알고리즘
제일 큰 수가 뒤로 가게 정렬한다.
이중 반복문으로 첫 번째 반복을 실행하면 제일 큰 수가 맨 끝에 위치하고 두 번째 반복문을 실행하면 두 번째로 큰 수가 뒤에서 두 번째에 위치한다.

외부 반복문을 배열의 마지막 인덱스(배열의 길이 -1)부터 0보다 클 때까지 반복한다. 내부 반복문은 0부터 i보다 작을 때까지 반복한다.

function bubbleSort(arr) {
  const swap = (arr, idx1, idx2) => {
    [arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]];
  };

  let noSwaps = true;
  for (let i = arr.length - 1; i > 0; i--) {
    for (let j = 0; j < i; j++) {
      if (arr[j] > arr[j + 1]) {
        swap(arr, j, j + 1);
      }
      noSwaps = false;
    }
  }
  return arr;
}
  
const arr = bubbleSort([8, 1, 2, 3, 4, 5, 6, 7]);
console.log(arr);   // [1,2,3,4,5,6,7,8]

불필요한 반복을 배제하기 위해 배열의 요소를 한번도 교환하지 않았다면 noSwaps를 true로 초기화하여 판별할 수 있다.
값을 교환한 경우 false로 변경한다. noSwaps가 true일 경우, 반복문을 빠져 나온다.

시간 복잡도

최고의 경우: $O(n)$
평균의 경우: $O(n^2)$
최악의 경우: $O(n^2)$

완전히 정렬되지 않은 배열의 경우 이중 반복문을 여러 번 반복해야 하므로 $O(n^2)$의 시간 복잡도를 가진다.

공간 복잡도: $O(1)$