거품 정렬🧺

소개

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

 

정렬 과정

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

 

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

 

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

 

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

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

 

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

 

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

 

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

 

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

 

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

 

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

 

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

 

연속해서 검사를 시작한다.

 

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

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

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

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

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

 

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

 

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

 

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

 

알고리즘 분석

비교 횟수

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

 

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

 

$$

(n - 1) + (n - 2) + ... + 2 + 1 = (n - 1) * n / 2 = \frac{n(n - 1)} {2}

$$

 

자리 교환 횟수

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

 

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

 

따라서 평균적으로 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;
			}
		}
	}
}

 

정리

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

 

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

 

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

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