3.2Bubble Sort

Bubble Sort

A sorting algorithm where the largest values bubble up to the top.

버블 정렬은 가장 큰 값이 반복을 거치며 점차 배열의 끝으로 밀려나는 정렬 알고리즘이다.

원리는 다음과 같다.

1. 우선, 첫 두 요소를 비교한다. 더 큰 데이터를 뒤에 보낸다.
2. 두번째와 세번째 요소를 비교한다. 더 큰 데이터를 뒤에 보낸다. 즉, 만약 첫번째 요소가 1~3번째 요소 중 가장 큰 데이터였으면 가장 뒤에 간다.
3. 같은 방식으로 끝까지 진행한다. 가장 큰 데이터가 가장 뒤에 있게 된다.
4. 처음부터 반복한다.

마치 큰 값이 거품처럼 위로 올라간다고 해서 버블 정렬이라는 이름이 붙었다.

자바스크립트로 단순하게 구현하면 아래와 같다. 배열 안의 요소들을 루프하며 계속 배열의 크기를 줄여나가야하고, 버블 정렬은 맨 뒤의 요소들부터 확정되기 때문에 i를 arr.length로 할당하고 점점 줄여가는 방식으로 구현한다. 즉,

• 바깥 루프는 정렬되지 않은 요소 개수를 점점 줄여가면서 반복
• 안쪽 루프는 인접한 요소를 비교해 더 큰 값을 뒤로 보냄

javascript
function bubbleSort(arr){
  for(let i = arr.length; i > 0; i--){
    for(let j = 0; j < i--; j++){
      // 앞의 요소가 더 크면 앞뒤 순서 바꾸기
      if(arr[j] > arr[j + 1]){
        let temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }
  return arr;
}

bubbleSort([37, 45, 29, 8];)
// [8, 29, 37, 45]

참고로, 순서를 바꾸는 swap 로직은 ES6부터는 아래와 같은 코드로도 가능하다.

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

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

버블 정렬 최적화

앞서 살펴본 방식은 좀 더 개선될 수 있다. 아래의 경우를 생각해보자.

javascript
bubbleSort([8, 1, 2, 3, 4, 5, 6, 7]);

가장 큰 요소인 8이 첫 루프에서 맨 뒤로 가고 나면 정렬은 완료되었지만, 우리의 코드는 계속해서 루프를 처음부터 진행한다.

사실 버블 정렬을 진행할 경우, 루프 도중 일단 정렬이 다 되고 나면 그 다음은 계속 앞뒤의 순서를 굳이 바꾸지 않는 무의미한 루프가 반복될 뿐이다. 따라서 이 무의미한 루프가 진행되지 않도록 루프를 끊는 로직이 들어가면 성능을 개선할 수 있다.

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

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

버블 정렬은 대개 O(n^2)의 시간 복잡도를 가진다. 하지만 우리가 마지막에 개선한 성능 버전으론, 정렬이 어떻게 되어 있냐에 따라 O(n)으로 아주 빠른 정렬을 할 수도 있다.