[Algorithm] 버블 정렬 (Bubble Sort)

버블 정렬은 인접한 원소를 비교하여 정렬하는 정렬 알고리즘입니다.

이 모습이 거품 같다고 해서 버블 정렬이라는 이름이 붙었습니다.

 

다음과 같은 순서로 이루어집니다.

1. n번째와 n+1번째 원소 비교
2. n+1이 끝에 도달할 때 까지 비교
3. 위 과정을 배열 원소의 개수만큼 반복

[그림 1] 예제 배열

[그림 1] 배열이 있다고 했을 때, 오름차순으로 버블정렬을 해 보겠습니다.

 

1. n번째와 n+1번째 원소 비교

[그림 2] 인접한 원소를 비교하는 모습

[그림 2]처럼 첫 번째부터 비교하면 됩니다.

[그림 3] 비교 후 swap하는 모습

두 번째 원소가 더 작기 때문에 서로 swap합니다.

[그림 4] 인접한 원소를 비교하는 모습

이제 두 번째 원소, 세 번째 원소를 비교하면 됩니다.

끝나면 세 번째, 네 번째 비교, 또 끝나면 네 번째, 다섯 번째...

 

2. n+1이 끝까지 도달할 때 까지 반복

[그림 5] 마지막으로 인접한 원소를 비교하는 모습

계속 비교를 하다 보니 제일 큰 숫자인 13이 맨 뒤로 갔습니다.

첫 번째 정렬이 완료된 것입니다.

 

3. 위 과정을 배열 원소의 개수만큼 반복

[그림 6] 인접한 원소를 비교하는 모습

이제 다시 첫 번째로 돌아와서 비교를 또 합니다.

이 때 맨 뒤 부분은 정렬이 완료되었으니, 그 앞 부분까지만 비교하면 됩니다.

[그림 7] 인접한 원소를 비교하는 모습

계속 반복하면 뒤에서부터 정렬이 됩니다.

2번 반복해서 2개가 정렬되었으니, 6번을 반복하면 정렬이 완료됩니다.

(그 전에 정렬이 완료되는 경우가 있긴 한데, 우연의 일치이기 때문에 컴퓨터가 알아차릴 방법이 없습니다.)

 

 

[그림 8] 정렬이 완료된 모습

정렬이 완료된 모습입니다.

 

예시를 통해 과정을 살펴보았을 때, 조건에 맞을 때마다 swap이 이루어지는 모습을 확인할 수 있습니다.

이로 인해 버블 정렬이 효율성이 좋지는 않습니다.

 

---

C++로 작성된 버블 정렬 알고리즘 코드입니다.

#include <iostream>
#define SIZE 6
using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	
	/* 배열 정의 */ 
	int arr[SIZE] = {13, 5, 9, 4, 6, 7};
	
	/* 개수가 n개이면 n - 1번 반복합니다. n번 반복해도 상관없습니다. */ 
	for(int i = 0; i < SIZE - 1; i++) { 
		/* 정렬 완료된 부분을 제외하고 반복 */ 
		for(int j = 0; j < SIZE - i - 1; j++) {
			/* 비교 후 조건에 따라 swap */ 
			if(arr[j] > arr[j + 1]) {
				int tmp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = tmp;
			}
		}
	}
	
	for(int i = 0; i < n; i++) cout << arr[i] << ' ';
}

[그림 9] 실행 결과

정렬이 되었음을 확인할 수 있습니다.