[JS 알고리즘] 버블 정렬(Bubble sort)

• 버블 정렬은 느려서 효율적이기 않기 때문에 잘 쓰이지 않는다. 하지만 어떻게 작동하는지 알면 왜 다른 알고리즘들이 이것보다 더 나은지 이해하는 데에 도움이 된다.

버블 정렬의 작동 방식

• 각 요소를 루프로 돌면서, 다음 요소가 비교하는 값보다 큰 지를 확인하고 그렇다면 자리를 바꾸는 과정(swap)을 반복한다. 즉, 바로 옆에 있는 것과 비교해서 크면 자리를 바꾼다.
• 값들이 차례로 버블을 타고 본인의 크기에 맞는 가장 위로 올라가는 방식으로 리스트가 재배열된다.
• 즉, 가장 큰 값이 위로 버블링되는 정렬 알고리즘이다.
• 정렬 전에, SWAP부터 제대로 알아야 한다.
  • 많은 정렬 알고리즘에는 일부 유형의 SWAP 기능이 포함되어 있다.

 // ES5
function swap(arr, idx1, idx2) {
  let temp = arr[idx1];
  arr[idx1] = arr[idx2];
  arr[idx2] = temp;
}

// ES6
const swap = (arr, idx1, idx2) => {
  [arr[idx1],arr[idx2]] = [arr[idx2],arr[idx1]];
}

버블 정렬 의사 코드

• i라는 변수로 배열의 끝에서부터 반복문을 시작한다.
  - 처음부터 i-1까지 j라는 변수로 내부 루프를 시작한다.
  - arr[j]가 arr[j+1]보다 크면 두 값을 교환한다.
• 정렬된 배열 반환

버블 정렬 코드

function bubbleSort(arr) {
  for (let i = arr.length; i > 0; i--) {
    for (let j = 0; j < i - 1; j++) {
      console.log(arr, arr[j], arr[j + 1]);
      if (arr[j] > arr[j + 1]) [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
    }
    console.log('one pass complete');
  }
  return arr;
}

const array = [5, 3, 12, 7, 14, 2];
console.log(bubbleSort(array));

/* 
[ 5, 3, 12, 7, 14, 2 ] 5 3
[ 3, 5, 12, 7, 14, 2 ] 5 12
[ 3, 5, 12, 7, 14, 2 ] 12 7
[ 3, 5, 7, 12, 14, 2 ] 12 14
[ 3, 5, 7, 12, 14, 2 ] 14 2
one pass complete
[ 3, 5, 7, 12, 2, 14 ] 3 5
[ 3, 5, 7, 12, 2, 14 ] 5 7
[ 3, 5, 7, 12, 2, 14 ] 7 12
[ 3, 5, 7, 12, 2, 14 ] 12 2
one pass complete
[ 3, 5, 7, 2, 12, 14 ] 3 5
[ 3, 5, 7, 2, 12, 14 ] 5 7
[ 3, 5, 7, 2, 12, 14 ] 7 2
one pass complete
[ 3, 5, 2, 7, 12, 14 ] 3 5
[ 3, 5, 2, 7, 12, 14 ] 5 2
one pass complete
[ 3, 2, 5, 7, 12, 14 ] 3 2
one pass complete
one pass complete
[ 2, 3, 5, 7, 12, 14 ] 
*/

• 참고로 위 코드가 아래 코드보다 효율적이다.(for문 조건 최적화)

function bubbleSort(arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length; j++) {
      if (arr[j] > arr[j + 1]) [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
    }
  }
  return arr;
}

const array = [5, 3, 12, 7, 14, 2];
console.log(bubbleSort(array));
/*
[ 5, 3, 12, 7, 14, 2 ] 5 3
[ 3, 5, 12, 7, 14, 2 ] 5 12
[ 3, 5, 12, 7, 14, 2 ] 12 7
[ 3, 5, 7, 12, 14, 2 ] 12 14
[ 3, 5, 7, 12, 14, 2 ] 14 2
[ 3, 5, 7, 12, 2, 14 ] 14 undefined
one pass complete
[ 3, 5, 7, 12, 2, 14 ] 3 5
[ 3, 5, 7, 12, 2, 14 ] 5 7
[ 3, 5, 7, 12, 2, 14 ] 7 12
[ 3, 5, 7, 12, 2, 14 ] 12 2
[ 3, 5, 7, 2, 12, 14 ] 12 14
[ 3, 5, 7, 2, 12, 14 ] 14 undefined
one pass complete
[ 3, 5, 7, 2, 12, 14 ] 3 5
[ 3, 5, 7, 2, 12, 14 ] 5 7
[ 3, 5, 7, 2, 12, 14 ] 7 2
[ 3, 5, 2, 7, 12, 14 ] 7 12
[ 3, 5, 2, 7, 12, 14 ] 12 14
[ 3, 5, 2, 7, 12, 14 ] 14 undefined
one pass complete
[ 3, 5, 2, 7, 12, 14 ] 3 5
[ 3, 5, 2, 7, 12, 14 ] 5 2
[ 3, 2, 5, 7, 12, 14 ] 5 7
[ 3, 2, 5, 7, 12, 14 ] 7 12
[ 3, 2, 5, 7, 12, 14 ] 12 14
[ 3, 2, 5, 7, 12, 14 ] 14 undefined
one pass complete
[ 3, 2, 5, 7, 12, 14 ] 3 2
[ 2, 3, 5, 7, 12, 14 ] 3 5
[ 2, 3, 5, 7, 12, 14 ] 5 7
[ 2, 3, 5, 7, 12, 14 ] 7 12
[ 2, 3, 5, 7, 12, 14 ] 12 14
[ 2, 3, 5, 7, 12, 14 ] 14 undefined
one pass complete
[ 2, 3, 5, 7, 12, 14 ] 2 3
[ 2, 3, 5, 7, 12, 14 ] 3 5
[ 2, 3, 5, 7, 12, 14 ] 5 7
[ 2, 3, 5, 7, 12, 14 ] 7 12
[ 2, 3, 5, 7, 12, 14 ] 12 14
[ 2, 3, 5, 7, 12, 14 ] 14 undefined
one pass complete
[ 2, 3, 5, 7, 12, 14 ] 
*/

버블 정렬 최적화

• 이미 정렬되어 있는 부분도 루프에서 정해준 대로 순회한다면 비효율적이다.
• 최적화하는 방법은 간단하다. 지난 번 순회에서 자리를 바꿨는지(swap) 확인하는 것이다.
  • 만약 지난 번 순회에서 자리를 바꾸지 않았다면 이미 정렬되어 있다는 의미이고, 이제 할 일이 다 끝났으므로 반복문을 break한다.

    function bubbleSort(arr) {
      let noSwaps;
      for (let i = arr.length; i > 0; i--) {
        noSwaps = true;  // 외부 for 문 돌 때마다 이전 swap 기록 초기화
        for (let j = 0; j < i - 1; j++) {
          console.log(arr, arr[j], arr[j + 1]);
          if (arr[j] > arr[j + 1]) {
            [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
            noSwaps = false; // 이번 순회에서 swap했다면 false 할당
          }
        }
        console.log('one pass complete');
        console.log(noSwaps);
        if (noSwaps) break; // 지난 번 순회에서 swap하지 않았다면(true) 루프를 break;
      }
      return arr;
    }
    
    const array = [9, 1, 2, 3, 4, 5];
    console.log(bubbleSort(array));
    
    /* 
    [ 9, 1, 2, 3, 4, 5 ] 9 1
    [ 1, 9, 2, 3, 4, 5 ] 9 2
    [ 1, 2, 9, 3, 4, 5 ] 9 3
    [ 1, 2, 3, 9, 4, 5 ] 9 4
    [ 1, 2, 3, 4, 9, 5 ] 9 5
    one pass complete
    false
    [ 1, 2, 3, 4, 5, 9 ] 1 2
    [ 1, 2, 3, 4, 5, 9 ] 2 3
    [ 1, 2, 3, 4, 5, 9 ] 3 4
    [ 1, 2, 3, 4, 5, 9 ] 4 5
    one pass complete
    true
    [ 1, 2, 3, 4, 5, 9 ]
     */

버블 정렬의 성능

• Best Case : O(n)
  • 데이터가 거의 정렬되어 있고 위에서 noSwaps 기능까지 포함한 버블 정렬을 사용한 경우
• Worst Case: $O(n^2)$