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

버블 정렬이란 ?

버블 정렬은 이름처럼 데이터가 아래로부터 서서히 올라오는 것 같은 모습이라 해서 버블 정렬이라고 이름을 붙였다.

 

해당 알고리즘은 데이터들을 순회하면서 이웃 요소들끼리 데이터를 교환하며 정렬을 수행합니다.

 

구현하기 쉬운만큼 성능은 그만큼 안좋기 때문에 실제로는 사용이 거의 불가능한 수준이므로 공부용이 아니라면 볼일이 거의 없을것이다.

버락 오바마는 2008년 대선 캠페인을 위해 구글 플렉스를 방문했을때, 청중 앞에서 에릭 슈미트가 그에게 32비트 정수 백만 개를 정렬하기 위한 가장 효율적인 방법을 물었을때 버락오바마는 이렇게 대답했습니다.

"버블 정렬은 아닌 것 같네요."

---

원리

버블 정렬은 아래와 같은 알고리즘으로 동작합니다.

1. 첫 번째 요소부터 시작해서 첫 번째 요소와 두 번째 요소, 두 번째 요소와 세 번째 요소 네 번째 요소와 다섯 번째 요소 ... (N-1) 요소와 N 요소끼리 비교하여 조건에 맞다면 서로 교환을 한다.
2. 이렇게 교환을 하게되면 가장 큰 숫자가 맨 뒤로 넘거가게 되어 해당 요소는 비교할 필요가 없다. 그러기 때문에 순환이 끝날때마다 순환 횟수만큼 교환 횟수가 줄어 든다.
3. 이 것들을 반복해서 모든 요소가 정렬이 끝나면 버블 정렬은 종료된다.

BubbleSort.gif

---

시간 복잡도

해당 알고리즘의 시간 복잡도를 계산해보면 (n-1) + (n-2) + (n-3) + ... + 3 + 2 + 1 = n(n-1) / 2 가 되므로 O(n^2) 입니다.

버블 정렬은 모든 요소를 확인하며 비교하기 때문에, 최소, 평균, 최악의 경우 모두 시간 복잡도가 O(n^2) 으로 동일하다.

---

소스코드

#include <stdio.h>

void BubbleSort(int _dataset[], int _length);

int main(void)
{
	int dataset[] = {6, 4, 2, 3, 1, 5};
	int length = sizeof(dataset) / sizeof(int);
	int i = 0;

	BubbleSort(dataset, length);
	
	for(i = 0; i < length; i++)
	{
		printf("%d ", dataset[i]);
	}
	
	
	return 0;
}

void BubbleSort(int _dataset[], int _length)
{
	for(int i = 0; i < _length; i++)
	{
		for(int j = 0; j < _length - i - 1; j++)
		{
			if(_dataset[j] > _dataset[j+1])
			{
				int temp = _dataset[j+1];
				_dataset[j+1] = _dataset[j];
				_dataset[j] = temp;
			}
		}
	}	
}