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

알고리즘

버블 정렬(Bubble Sort)의 알고리즘은 다음과 같습니다.

• 첫 번째 원소부터 마지막 원소까지 바로 옆에 있는 원소와 비교해 작은 값을 앞으로 옮겨줍니다.
• 첫 번째 원소부터 마지막 이전 원소까지 바로 옆에 있는 원소와 비교해 작은 값을 앞으로 옮겨줍니다.
• 정렬될 때까지 이를 반복

예를 들어 다음 배열을 정렬해 보겠습니다.

[4 , 6 , 8 , 1 , 3 , 5 , 7 , 2 , 10 , 9]

1-1)  4 와 6 비교해 4 <6이니 그대로

1-2)  6 과 8 비교해 6 <8이니 그대로

1-3)  8 과 1 비교해 8>1이니 8과 1 위치 변경

[4 , 6 , 8 , 1 , 3 , 5 , 7 , 2 , 10 , 9]

[4 , 6 , 1 , 8 , 3 , 5 , 7 , 2 , 10 , 9]

1-4)  1 과 3 비교해 1 <3이니 그대로

1-5)  3 과 5 비교해 3 <5이니 그대로

1-6)  5 와 7 비교해 5 <7이니 그대로

1-7)  7 과 2 비교해 7>2이니 7과 2 위치 변경

[4 , 6 , 1 , 8 , 3 , 5 , 7 , 2 , 10 , 9]

[4 , 6 , 8 , 1 , 3 , 5 , 2 , 7 , 10 , 9]

1-8) 7 과 10 비교해 7 <10이니 그대로

1-9) 10 과 9 비교해 10>9이니 10과 9 위치 변경

[4 , 6 , 8 , 1 , 3 , 5 , 2 , 7 , 10 , 9]

[4 , 6 , 8 , 1 , 3 , 5 , 2 , 7 , 9 , 10]

 

마지막에 10은 정렬된 상태

---

2-1) 4 와 6 비교해 4 <6이니 그대로

2-2) 6 과 8 비교해 6 <8이니 그대로

2-3) 8 과 1 비교해 8>1이니 8과 1 위치 변경

[4 , 6 , 8 , 1 , 3 , 5 , 2 , 7 , 9 , 10]

[4 , 6 , 1 , 8 , 3 , 5 , 2 , 7 , 9 , 10]

2-4) 8 과 3 비교해 8>3이니 8과 3 위치 변경

[4 , 6 , 1 , 8 , 3 , 5 , 2 , 7 , 9 , 10]

[4 , 6 , 1 , 3 , 8 , 5 , 2 , 7 , 9 , 10]

2-5) 8 과 5 비교해 8>5이니 8과 5 위치 변경

[4 , 6 , 1 , 3 , 8 , 5 , 2 , 7 , 9 , 10]

[4 , 6 , 1 , 3 , 5 , 8 , 2 , 7 , 9 , 10]

2-6) 8 과 2 비교해 8>2이니 8과 2 위치 변경

[4 , 6 , 1 , 3 , 5 , 8 , 2 , 7 , 9 , 10]

[4 , 6 , 1 , 3 , 5 , 2 , 8 , 7 , 9 , 10]

2-7) 8 과 7 비교해 8>7이니 8과 7 위치 변경

[4 , 6 , 1 , 3 , 5 , 2 , 8 , 7 , 9 , 10]

[4 , 6 , 1 , 3 , 5 , 2 , 7 , 8 , 9 , 10]

2-8) 8 과 9 비교해 8 <9이니 그대로

 

마지막에 9,10은 정렬된 상태

---

이렇게 전체 배열이 정렬될 때까지 반복합니다.

[1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10]

---

시간 복잡도

 

버블 정렬의 시간 복잡도는 O(N^2)입니다.

 

위의 예제를 예로 들어 왜 버블 정렬의 시간 복잡도가 O(N^2)인지에 대해 설명하겠습니다.

 

첫 번째 단계에서 10이라는 숫자를 제일 마지막에 배치할 때까지 9번의 비교가 있었습니다.

 

두 번째 단계에서 10이라는 숫자를 제외하고, 9를 10 이전에 배치할 때까지 8번의 비교가 있었습니다.

 

...

 

이렇게 10개의 숫자를 정렬하기 위해 비교한 횟수는 9번+8번+ ... + 0번입니다.

 

1부터 N-1까지의 합 공식을 적용하면 다음과 같습니다.

 

(N - 1) x N / 2

 

즉, 버블 정렬의 시간 복잡도는 O(N^2)입니다.

 

---

소스코드

위의 내용을 바탕으로 C++로 소스 코드로 작성해 보겠습니다.

 

#include <iostream>
using namespace std;

int main(void) {
	//정렬할 배열
	int array[10] = { 4,6,8,1,3,5,7,2,10,9 };
	//swap할때 사용할 변수
	int temp;
	
	//정렬할 배열의 크기만큼 반복
	for (int i = 0; i < 10; i++) {
		for (int j = 0; j < 9 - i; j++) {
			//먼저 나온 값이 이후 값보다 크면 Swap
			if (array[j] > array[j + 1]) {
				temp = array[j];
				array[j] = array[j + 1];
				array[j + 1] = temp;
			}
		}
	}

	for (int i = 0; i < 10; i++) {
		cout << array[i] << " ";
	}

	return 0;
}

 

위 코드를 실행시켜 보면 다음과 같이 정렬된 배열을 확인할 수 있습니다.

 

버블 정렬은 구현하기 쉽다는 장점을 갖고 있지만, 가장 효율성이 떨어지는 정렬 알고리즘입니다.

 

기존에 포스팅한 선택 정렬(Selection Sort)과 시간 복잡도는 O(N^2)로 동일합니다.

 

하지만 버블 정렬은 비교하는 동시에 자리를 바꿔주는 연산까지 하기 때문에 선택 정렬보다 비효율적입니다.