거품 정렬

소개

거품 정렬(Bubble sort)은 인접한 두 원소를 검사하여 정렬하는 방법입니다. 시간 복잡도가 O(n2)O(n^2) 로 상당히 느리지만, 코드가 단순해서 자주 사용됩니다. 이름의 유래는 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어졌습니다.

정렬 과정

다음과 같이 다섯 개의 정수가 주어졌을 때, 오름 차순으로 정렬해보겠습니다.

+-----+-----+-----+-----+-----+
|  5  |  4  |  1  |  3  |  2  |
+-----+-----+-----+-----+-----+
+-----+-----+-----+-----+-----+
|  5  |  4  |  1  |  3  |  2  |
+-----+-----+-----+-----+-----+

우선 인덱스 0의 값과 인덱스 1의 값을 비교하면, 인덱스 0의 값이 더 크기 때문에 두 값이 서로 교체됩니다.

+-----+-----+-----+-----+-----+
|  4  |  5  |  1  |  3  |  2  |
+-----+-----+-----+-----+-----+
+-----+-----+-----+-----+-----+
|  4  |  5  |  1  |  3  |  2  |
+-----+-----+-----+-----+-----+

이어서 인덱스 1의 값과 인덱스 2의 값을 비교해서 교체합니다.

+-----+-----+-----+-----+-----+
|  4  |  1  |  5  |  3  |  2  |
+-----+-----+-----+-----+-----+
+-----+-----+-----+-----+-----+
|  4  |  1  |  5  |  3  |  2  |
+-----+-----+-----+-----+-----+

이어서 인덱스 2의 값과 인덱스 3의 값을 비교해서 교체합니다.

+-----+-----+-----+-----+-----+
|  4  |  1  |  3  |  5  |  2  |
+-----+-----+-----+-----+-----+
+-----+-----+-----+-----+-----+
|  4  |  1  |  3  |  5  |  2  |
+-----+-----+-----+-----+-----+

이어서 인덱스 3의 값과 인덱스 4의 값을 비교해서 교체합니다.

+-----+-----+-----+-----+-----+
|  4  |  1  |  3  |  2  |  5  |
+-----+-----+-----+-----+-----+
+-----+-----+-----+-----+-----+
|  4  |  1  |  3  |  2  |  5  |
+-----+-----+-----+-----+-----+

초기 상태와 비교했을 때 첫 번째 원소였던 5가 가장 우측으로 이동한 것을 볼 수 있습니다.

이제 원소들을 끝까지 검사했으니 다시 처음으로 돌아가서 새롭게 검사를 시작합니다. 다만, 다음 검사부터 달라지는 점은 가장 큰 원소가 가장 우측으로 이동했기 때문에 다음 검사부터는 한 칸 전까지만(인덱스 3) 검사하면 됩니다.

연속해서 검사를 시작합니다.

+-----+-----+-----+-----+-----+
|  1  |  4  |  3  |  2  |  5  |
+-----+-----+-----+-----+-----+
+-----+-----+-----+-----+-----+
|  1  |  4  |  3  |  2  |  5  |
+-----+-----+-----+-----+-----+
+-----+-----+-----+-----+-----+
|  1  |  3  |  4  |  2  |  5  |
+-----+-----+-----+-----+-----+
+-----+-----+-----+-----+-----+
|  1  |  3  |  4  |  2  |  5  |
+-----+-----+-----+-----+-----+
+-----+-----+-----+-----+-----+
|  1  |  3  |  2  |  4  |  5  |
+-----+-----+-----+-----+-----+
+-----+-----+-----+-----+-----+
|  1  |  3  |  2  |  4  |  5  |
+-----+-----+-----+-----+-----+
+-----+-----+-----+-----+-----+
|  1  |  3  |  2  |  4  |  5  |
+-----+-----+-----+-----+-----+
+-----+-----+-----+-----+-----+
|  1  |  3  |  2  |  4  |  5  |
+-----+-----+-----+-----+-----+
+-----+-----+-----+-----+-----+
|  1  |  2  |  3  |  4  |  5  |
+-----+-----+-----+-----+-----+
+-----+-----+-----+-----+-----+
|  1  |  2  |  3  |  4  |  5  |
+-----+-----+-----+-----+-----+

마지막 표에서 인덱스 0과 인덱스 1의 검사도 끝난 것 같아 보이지만, 우리는 현재 가시적으로 값을 보고 있기 때문이고, 컴퓨터는 마지막 검사를 수행해야 합니다.

+-----+-----+-----+-----+-----+
|  1  |  2  |  3  |  4  |  5  |
+-----+-----+-----+-----+-----+
+-----+-----+-----+-----+-----+
|  1  |  2  |  3  |  4  |  5  |
+-----+-----+-----+-----+-----+

인덱스 0만 남은 경우에는 더 이상 검사를 해줄 필요가 없습니다. 이미 앞선 정렬에서 정렬을 완벽하게 수행했다면 가장 작은 원소만 남아있기 때문입니다.

알고리즘 분석

비교 횟수

거품 정렬은 한 번의 검사마다 비교 대상이 하나씩 줄어듭니다. 전체 원소의 개수가 nn 개면, 총 (n−1)(n - 1) 번 검사하면 한 번 정렬이 완료됩니다.

앞 선 예제에서 총 원소가 5개 이므로, 4+3+2+1=104 + 3 + 2 + 1 = 10 번 검사하면 전체 정렬이 완료됩니다. 이를 수식으로 일반화하면 다음과 같습니다.

(n−1)+(n−2)+...+2+1=(n−1)∗n/2=n(n−1)/2(n - 1) + (n - 2) + ... + 2 + 1 = (n - 1) * n / 2 = n(n - 1) / 2

자리 교환 횟수

최선의 경우(이미 정렬된 원소들이 주어지는 경우), 자리 교환이 이루어지지 않기 때문에 시간 복잡도에 영향이 없습니다.

그러나 최악의 경우(역순 정렬된 원소들이 주어지는 경우), 모든 검사에서 자리 교환이 이루어집니다. 이 경우 최대 비교 횟수인 (n−1)∗n/2(n - 1) * n / 2 번이 됩니다.

따라서 평균적으로 O(n2)O(n^2) 의 시간 복잡도를 가집니다.

구현

앞 선 예제를 코드로 구현하면 다음과 같습니다.

void bubble_sort(int *array) {
  int temp;

  for (int i = 0; i < SIZE - 1; i++) {
    for (int j = 0; j < SIZE - i - 1; j++) {
      if (array[j] > array[j + 1]) {
        temp = array[j];
        array[j] = array[j + 1];
        array[j + 1] = temp;
      }
    }
  }
}
void bubble_sort(int *array) {
  int temp;

  for (int i = 0; i < SIZE - 1; i++) {
    for (int j = 0; j < SIZE - i - 1; j++) {
      if (array[j] > array[j + 1]) {
        temp = array[j];
        array[j] = array[j + 1];
        array[j + 1] = temp;
      }
    }
  }
}

정리

거품 정렬은 직관적으로 이해할 수 있고, 코드도 단순합니다. 그러나 높은 시간 복잡도 때문에 데이터의 양이 많은 경우에 성능이 저하됩니다.

예제에서는 5개의 원소를 정렬하여 10번의 검사를 수행했지만, 1억 개의 원소를 정렬하는 경우에는 약 5,000조 번 검사를 수행해야 합니다. 이는 퀵 정렬보다 약 천만 배 느립니다.

추가로 거품 정렬을 개선하는 방법은 여러 가지가 있습니다.

최선의 경우를 검사해서 정렬을 사용하지 않는 방법, 거품 정렬을 양방향으로 수행하는 칵테일 셰이커 정렬(cocktail shaker sort), 특정한 감소량(shrink factor)에 의해 차이(gap)를 줄여가며 정렬하는 빗질 정렬(comb sort) 등이 있습니다.