Bubble sort

반복문을 이용해 인접한 두 요소를 비교하며 조건에 부합하면 자리를 교환하며 정렬한다.

반복문 중간에 boolean 값을 리턴하는 변수를 추가하여 연산을 줄일 수 있다.

예제 코드

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

  let noSwap;
  for(let i = arr.length; i > 0; i--) {
    noSwap = true;
    for(let j = 0; j < i - 1; j++) {
      if(arr[j] > arr[j + 1]) {
        swap(arr, j, j + 1);
        noSwap = false;
      }
    }
    if(noSwap) break;
  }

  return arr;
}

시간 복잡도: O(n^2)

공간 복잡도: O(n)