Daily Coding - bubbleSort

내가 쓴 코드

const bubbleSort = function (arr) {
  // TODO: 여기에 코드를 작성합니다.
  let small
  for(let i =0; i <arr.length; i++) {
    console.log(arr)
    for(let j=0; j < arr.length; j++) {
      if(arr[j] > arr[j+1]){
        small = arr[j]
        arr[j] = arr[j+1]
        arr[j+1] = small
        console.log(arr[j])
      }
    }
  }
};

레퍼런스 코드

let swaps = 0;

if (arr[j] > arr[j + 1]) {
        swaps++;
  }
if (swaps === 0) {
      break;
    }

레퍼런스코드의 핵심 코드는 이 문장이다.

내가 처음 푼 코드의 실행결과를 보자. 첫번째 for문이 끝났을 때 이미 정렬이 완료되었다. 하지만 for문은 배열의 길이만큼 돌아야 하기 때문에 계속해서 실행되어야 하기 때문에 시간복잡도가 늘어난다. 여기서 swaps의 초기값인 0을 설정하고 정렬이 일어날 때 마다 swaps의 크기를 1씩 증가시킨다. 그런데 만약 정렬이 한번도 일어나지 않아 swaps가 0이라면 첫번째 for문을 탈출하여 for문을 종료시킨다. 이렇게 시간복잡도를 줄일 수 있다.