[알고리즘] 버블 정렬 알고리즘

정렬은 자료 탐색에서 매우 중요한 알고리즘이다. 국어사전을 예로 들어보자 만약 국어사전이 가나다 순으로 오름차순이나 내림차순 정렬이 되어 있지 않다면 단어를 빨리 찾는 것은 매우 어려울 것이다. 정렬 알고리즘은 여러 가지가 있지만 이번에 다룰 알고리즘은 버블 정렬 알고리즘이다.

1. 버블 정렬 알고리즘이란?

버블 정렬은 인접한 두 개의 값을 비교한 후 크기가 순서대로 되어 있지 않을 경우 두 값을 서로 교환하는 방법이다. 오름차순으로 정렬한다고 가정하고 설명해보겠다.

위의 그림은 버블 정렬로 한 번의 스캔을 하는 과정이다. 이렇게 인접한 두 값을 비교해 오른쪽 끝까지 진행하면 한 번의 스캔이 끝났을 때에는 가장 큰 값이 오른쪽 끝에 위치하게 된다.

이제 검정색으로 표시한 정렬이 된 부분과 파란색으로 표시한 정렬이 안된 부분이 남게 된다.

정렬이 안된 부분에 대해서 이렇게 계속 스캔을 해주면 된다. 그때마다 정렬이 안된 부분 중 가장 큰 값이 오른쪽 끝에 위치할 것이다.

최종적으로 이렇게 정렬이 완료된다.

2. 소스 코드 구현

구현하는데 사용한 언어는 C++이다.

void bubble_sort(int* arr, int n) {
	for (int i = n - 1; i > 0; i--) {
		for (int j = 0; j < i; j++) {
			if (arr[j] > arr[j + 1]) {
				swap(arr[j], arr[j + 1]);
			}	// 앞 뒤의 값을 비교한 후 교환
		}
	}
}

i는 처음에 배열의 끝 인덱스를 가리킬 것이다. i가 가리키는 인덱스까지 안쪽 for문에서 스캔을 수행할 것이며, 스캔이 끝날 때마다 i가 가리키는 인덱스는 한 칸씩 앞으로 오게 된다. 결국 i의 값이 1을 가리킬 때 정렬이 끝나게 된다.

하지만 예를 들어 1, 3, 4, 5, 9, 7 처럼 이미 앞부분이 정렬이 완료된 경우에는 스캔을 꼭 다할 필요는 없을 것이다. 따라서 이런 식으로 개선이 가능하다.

void bubble_sort(int* arr, int n) {
	bool isSorted = false;

	for (int i = n - 1; i > 0 && !isSorted; i--) {
		isSorted = true;
		for (int j = 0; j < i; j++) {
			if (arr[j] > arr[j + 1]) {
				swap(arr[j], arr[j + 1]);
				isSorted = false;
			}	// 앞 뒤의 값을 비교한 후 교환
		}
	}
}

이런식으로 플래그를 하나 만들어 사용한다면 불필요한 스캔을 줄일 수 있다.

#include <iostream>
using namespace std;

void print_array(int* arr, int n) {
	for (int i = 0; i < n; i++) {
		cout << arr[i] << " ";
	}
	cout << endl;
}

void bubble_sort(int* arr, int n) {
	for (int i = n - 1; i > 0; i--) {
		for (int j = 0; j < i; j++) {
			if (arr[j] > arr[j + 1]) {
				swap(arr[j], arr[j + 1]);
			}	// 앞 뒤의 값을 비교한 후 교환
		}
	}
}

int main() {
	int arr[6] = { 5, 2, 9, 4, 3, 1 };
	cout << "정렬 전 -> ";
	print_array(arr, 6);

	cout << "정렬 후 -> ";
	bubble_sort(arr, 6);
	print_array(arr, 6);

	return 0;
}

예제를 실행시킬 수 있는 전체 코드이다.

3. 관련 포스트

[알고리즘] 삽입 정렬 알고리즘
[알고리즘] 선택 정렬 알고리즘

4. 참조

천인국, 최영규, 「C++로 쉽게 풀어쓴 자료구조」, 생능출판사, 2019년