[#1] 버블 정렬 (Bubble Sort)

버블 정렬이란?

버블 정렬 또는 거품 정렬(bubble sort 버블 소트, sinking sort 싱킹 소트)은 정렬 알고리즘 중 하나이다.
시간 복잡도가 O(n2)로 상당히 느리지만, 코드가 단순하기 때문에 자주 사용된다.
원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어진 이름이다.
- 위키 백과

 

 

 

 

구현 방법

탐색은 2중 for문으로 구성되며, 바깥 fot문의 인덱스를 기준으로 안쪽 for문으로 비교 탐색하면서 탐색 마지막에 도달했을 때 해당 결과를 반영하는 방식이다. 

 

 

 

---

의사 코드

1. 첫 번째 인덱스부터 마지막 인덱스까지 탐색한다.
   1. 인덱스를 탐색할 때마다 0부터 size - 탐색 중인 인덱스만큼 탐색한다.
   2. 현재 탐색중인 인덱스의 원소와 인덱스의 원소 + 1를 서로 비교한다.
   3. 대소 관계에 따라 Swap한다.

 

 

 

---

소스 코드

void BubbleSort(char* input, int size)
{
	if (input == 0 || size <= 1)
		return;

	int i, j;
	int strSize = size - 1;
	for (i = 0; i < strSize; ++i)
	{
		for (j = 0; j < strSize - i; ++j)
		{
			if (input[j] > input[j + 1])
			{
				SWAP(input[j], input[j + 1], char);
			}
		}
	}
}

 

 

 

---

시간 복잡도

T(n) = (n-1) + (n-2) + (n3) ... + 1
T(n) = (n-1) * n/2 이므로,
O(n) = n^2 이다. (최고차항만 취급하므로)

 

 

 

---

안정성 제자리

원소의 값이 같을 경우 그 순서가 변하지 않으므로 버블 정렬은 안정 정렬(Stable Sort)이다.
또한, 기존 배열 이외에 추가적인 메모리를 사용하지 않으므로 제자리 정렬(in-place sort)이다.

 

 

 

---