[알고리즘] 버블정렬 Bubble Sort (C++ 구현)

코테 문제를 풀면서 꼭 필요한 알고리즘 기법 중 하나가 정렬이라고 할 수 있다.

일반적으로 문제에 따라 (시간복잡도를 고려한) 적절한 정렬 알고리즘을 공식처럼 사용한다.

 

그 전에 자주 쓰는 정렬 알고리즘 종류와 시간복잡도를 계산했다.

---

📌 버블정렬 (Bubble Sorting)

맨 왼쪽 원소부터 바로 이웃한 오른쪽 원소와 비교해가며 큰 수가 오른쪽으로 가도록 교환하는 정렬방식이다. 거품정렬이라고도 하며 두 인접한 원소를 비교하는 것이 핵심이다. 시간복잡도는 O(n^2)이지만 구현이 쉬워 자주 사용된다.

TMI) 양방향으로 번갈아 수행하면 칵테일 정렬이라고 한다.

 

이해하기 쉽도록 { 8, 3, 9, 7 6 } 배열을 오름차순 정렬하는 것을 예로 들었다.

버블정렬은 이해하기도 쉽고 구현하기도 쉬워서 자주 쓰이는데 아래 그림을 보면 이유를 알 수 있다.

말 그대로 맨 왼쪽 원소부터 바로 이웃한 다음 원소와 비교해가며 큰 수가 오른쪽으로 가도록 교환한다.

이해하기 쉽게 '라운드' 라고 썼는데 매번 가장 큰 원소를 찾는 과정을 반복하기 때문에 그 반복 횟수별로 라운드라고 해줬다. 구현하기 쉽게 0 라운드부터 시작한다. 

버블정렬 예시

5개의 숫자를 정렬하므로 n = 5라고 본다면 0라운드에서는 n-1번 비교, 1라운드에서는 n-2번 비교, 2라운드에서는 n-3번 비교, 3라운드에서는 n-4=1번 비교를 한다. 오름차순 정렬이므로 매 라운드마다 정렬되지 않은 숫자들 중 최댓값이 가장 오른쪽에 배치된다. 초록색 숫자로 표시해뒀는데, 매 라운드마다 9, 8, 7, 6 의 숫자가 차례대로 정렬된 것을 알 수 있다. 이 때문에 라운드별 비교 횟수가 n-1, n-2, n-3, ..., 1 이 되는 것이다. 

 

📌 시간복잡도

이에 대해 시간복잡도도 따져볼 수 있다. 일반화 시켜보면 n개의 원소에 대해 맨 처음엔 n-1번 비교, 다음은 n-2번 비교, ... 마지막은 1번만 비교하면 되므로 다음과 같이 식을 작성할 수 있다. 

버블정렬의 n^2 시간복잡도를 가지는 대표적인 정렬기법이다. 버블정렬은 입력 배열의 정렬여부에 상관없이 항상 똑같은 횟수만큼 비교하므로 시간복잡도도 일정하다.

 

📌 C++ 구현

#include <iostream>
#include <vector>
using namespace std;

vector<int> bubble_sort(vector<int> target) {
	int n = target.size();
	int temp;
	for (int i = 0; i < n - 1; i++) {
		for (int j = 0; j < n - i - 1; j++) {
			if (target[j] > target[j + 1]) {
				temp = target[j];
				target[j] = target[j + 1];
				target[j + 1] = temp;
			}
		}

		// i번째 정렬 결과 출력
		for (int c = 0; c < n; c++) {
			cout << target[c] << " ";
		}
		cout << endl;
	}
	return target;
}

int main(void) {
	int n = 5;
	vector<int> target = { 5, 3, 1, 4, 2 };
	auto result = bubble_sort(target);

	// 최종 정렬 결과 출력
	cout << endl;
	for (int i = 0; i < n; i++) {
		cout << result[i] << " ";
	}

	return 0;
}

입력되는 배열의 길이가 일정하지 않을 것이므로 vector를 사용해 구현했다.

인접한 두 원소의 값을 교환하는(swap) 함수를 따로 만들어 기능을 분리해도 괜찮을 것 같다.

(좌) { 8, 3, 9, 7, 6 } 정렬, (우) { 5, 3, 1, 4, 2, 9, 8, 0, 7, 6 } 정렬

 

다음은 삽입정렬이다.