[자료구조] 버블 정렬

버블 정렬이란?

  매우 기본적인 정렬 알고리즘인 버블 정렬(Bubble sort)은 이해하기 쉽기 때문에 단순 정렬(simple sort)이라 불린다. 다만 빠르다고 알려진 정렬 알고리즘보다는 비효율적이다.

  버블 정렬은 다음과 같은 단계를 따른다.

 

1. 배열 내에서 연속된 두 항목을 가리킨다. 첫 번째 항목과 두 번째 항목을 비교한다.

2. 두 항목의 순서가 뒤바뀌어 있으면 (왼쪽 값이 오른쪽 값보다 크면) 두 항목을 교환(swap)한다.
   순서가 올바르다면 아무것도 하지 않는다.

3. 비교 위치(포인터)를 오른쪽으로 한 셀씩 옮긴다.

4. 더 이상 교환하지 않을 때까지 1단계부터 3단계까지 반복한다. 더는 교환을 하지 않는다는 것은 배열이 정될된 상태라는 뜻이며 1 ~ 3 단계를 반복하는 것을 패스스루(passthrough)라고 부른다.

버블 정렬 구현

C++로 다음과 같이 구현할 수 있다.

첫 번째 passtrough에서 가장 작은 값을 가장 왼쪽으로 옮겨 놓기 때문에 다음 passthrough에서는 두 번째 셀부터 비교하면 된다.

void bubble_sort(int* list, unsigned int len)
{
	bool bSorted = true;
	int search_index = 0;

	do {
		bSorted = true;
		for (int i = len - 1; i > search_index; i--)
		{
			if (list[i] < list[i - 1])
			{
				int temp = list[i];
				list[i] = list[i - 1];
				list[i - 1] = temp;
				bSorted = false;
			}
		}
		search_index++;
	} while (!bSorted);
}

int main()
{
	int list[7] = { 65, 55, 45, 35, 20, 51, 33 };
	bubble_sort(list, 7);

	for (int i = 0; i < 7; i++)
		std::cout << list[i] << std::endl;

    return 0;
}

뒤죽박죽으로 넣었지만, 정렬되어 출력함을 알 수 있다.

bubllesort.zip

0.01MB

버블 정렬의 효율성

  버블 정렬 알고리즘에 포함된 단계는 두 종류다.

• 비교 : 어느 쪽이 더 큰지 두 수를 비교한다.
• 교환 : 정렬하기 위해 두 수를 교환한다.

  버블 정렬에서는 얼마나 많은 비교가 일어나는지 알아보자. 원소가 5개인 배열로 가정하면, 첫 번째 패스스루에서 두 수의 비교를 4번 해야 한다. 그다음은 3번, 그다음은 2번, 그다음은 1번 하면 된다.

 

따라서,

4 + 3 + 2 + 1 = 10 번의 비교가 필요하다. 교환도 마찬가지다.

그래서 5개의 데이터를 버블 정렬할 때 최대 단계 수는 20이 된다.

 

데이터의 개수가 많아지면 기하급수적으로 늘어나기 때문에 비효율적인 알고리즘으로 간주된다.