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

버블 정렬이란?

버블 정렬은 배열의 요소들을 인접한 두 개씩 비교하며 정렬합니다. 두 요소를 비교하여 필요하다면 위치를 바꾸고, 이러한 과정을 배열의 끝까지 반복하면서 가장 큰 값(또는 작은 값)이 점차 배열의 끝으로 "떠오르는" 방식입니다.

간단한 동작 원리:

1. 배열의 첫 번째 요소부터 시작해 인접한 두 요소를 비교합니다.
2. 두 요소가 잘못된 순서라면(예: 오름차순 정렬에서 앞의 값이 뒤의 값보다 클 경우) 위치를 교환(swap) 합니다.
3. 배열 끝까지 이 과정을 반복하며, 가장 큰 값이 맨 끝에 위치합니다.
4. 위 과정을 배열의 길이가 점차 줄어들도록 반복하면 정렬이 완료됩니다.

---

버블 정렬의 동작 과정

배열 [64, 25, 12, 22, 11]을 버블 정렬로 오름차순 정렬하는 과정을 보겠습니다.

1. 첫 번째 반복(배열 전체 탐색)
   • 64와 25 비교 → 교환 → [25, 64, 12, 22, 11]
   • 64와 12 비교 → 교환 → [25, 12, 64, 22, 11]
   • 64와 22 비교 → 교환 → [25, 12, 22, 64, 11]
   • 64와 11 비교 → 교환 → [25, 12, 22, 11, 64]
   • 배열 끝에 가장 큰 값 64가 위치합니다.
2. 두 번째 반복(마지막 요소 제외)
   • 25와 12 비교 → 교환 → [12, 25, 22, 11, 64]
   • 25와 22 비교 → 교환 → [12, 22, 25, 11, 64]
   • 25와 11 비교 → 교환 → [12, 22, 11, 25, 64]
   • 배열 끝에서 두 번째 위치에 25가 자리 잡습니다.
3. 세 번째 반복(마지막 두 요소 제외)
   • 12와 22 비교 → 그대로 유지
   • 22와 11 비교 → 교환 → [12, 11, 22, 25, 64]
   • 배열 끝에서 세 번째 위치에 22가 자리 잡습니다.
4. 네 번째 반복(마지막 세 요소 제외)
   • 12와 11 비교 → 교환 → [11, 12, 22, 25, 64]
   • 배열이 완전히 정렬되었습니다.

---

버블 정렬의 코드 구현

C++로 구현한 버블 정렬 코드는 다음과 같습니다.

#include <iostream>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>
#include <algorithm>
using namespace std;

//배열 인덱스를 역으로 설정하여 구현하는 방법도 존재합니다.
//저는 정방향으로 구현해봤습니다.
void bubble_sort(int ary[], int size) {
	//총 반복 횟수만큼 반복
	for (int i = 0; i < size - 1; i++) {
		// 실질적으로 값 변경하는 반복문
		// 배열의 우측부터 점차 정렬되어지므로 반복횟수가 점차 줄어듭니다.
		// 이를 i를 빼어줌으로써 구현하였습니다.
		for (int j = 0; j < size - 1 - i; j++) {
			//현재 값과 다음 값 비교
			if (ary[j] > ary[j + 1]) {
				int temp = ary[j];
				ary[j] = ary[j + 1];
				ary[j + 1] = temp;
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int ary[5] = {64, 25, 12, 22, 11};
	bubble_sort(ary, 5);
	for (int i = 0; i < 5; i++)
		cout << ary[i] << ' ';

	return 0;
}