버블 정렬이란?
- *버블 정렬(Bubble Sort)**은 가장 기본적인 정렬 알고리즘 중 하나로,
인접한 두 원소를 비교하여 순서가 잘못되어 있으면 교환하는 과정을 반복하는 방식이다.
기본 정보
- 입력: 양의 정수 n개의 키를 가진 배열 data[0..n-1]
- 출력: 오름차순으로 정렬된 배열 data[0..n-1]
- 정렬 방식: In-place sort (추가 메모리 공간을 거의 사용하지 않음)
- 안정성: 안정 정렬 (Stable Sort)
버블 정렬이라 불리는 이유는
큰 원소가 배열의 끝으로 이동하는 모습이 마치 물속에서 기포(bubble)가 수면으로
떠오르는 것과 같다고 생각해서 그렇다고 한다....(.....진짜로..?)
동작 원리
1. 인접한 두 원소를 비교한다.
2. 순서가 잘못되어 있으면 교환한다.
3. 배열 끝까지 이 과정을 반복한다.
4. 한 번의 패스가 끝나면 가장 큰 원소가 맨 끝에 위치한다.
5. 정렬이 완료될 때까지 패스를 반복
단계별 동작 과정
예시 배열: [64, 34, 25, 12, 22, 11, 90]
Pass 1
[64, 34, 25, 12, 22, 11, 90]
↑ ↑ (64 > 34이므로 교환)
[34, 64, 25, 12, 22, 11, 90]
↑ ↑ (64 > 25이므로 교환)
[34, 25, 64, 12, 22, 11, 90]
↑ ↑ (64 > 12이므로 교환)
[34, 25, 12, 64, 22, 11, 90]
↑ ↑ (64 > 22이므로 교환)
[34, 25, 12, 22, 64, 11, 90]
↑ ↑ (64 > 11이므로 교환)
[34, 25, 12, 22, 11, 64, 90]
↑ ↑ (64 < 90이므로 교환 없음)
결과: 가장 큰 원소 90이 맨 끝에 위치
Pass 2
[34, 25, 12, 22, 11, 64, 90] ← 90은 이미 정렬됨
↑ ↑ (34 > 25이므로 교환)
[25, 34, 12, 22, 11, 64, 90]
↑ ↑ (34 > 12이므로 교환)
[25, 12, 34, 22, 11, 64, 90]
↑ ↑ (34 > 22이므로 교환)
[25, 12, 22, 34, 11, 64, 90]
↑ ↑ (34 > 11이므로 교환)
[25, 12, 22, 11, 34, 64, 90]
↑ ↑ (34 < 64이므로 교환 없음)
결과: 두 번째로 큰 원소 64가 올바른 위치
대충 이런식으로 계속 진행하면 최종적으로 정렬이 완료 됨.
코드 구현과 분석
기본 버전
#include <iostream>
#include <cassert>
#include <vector>
using namespace std;
class Sort {
protected:
vector<int> m_data;
int m_size;
public:
Sort() {}
~Sort() {}
void InitData(vector<int> data) {
m_data = data;
m_size = data.size();
}
void printall() {
for (int i = 0; i < m_size; i++) {
cout << m_data[i] << " ";
}
cout << endl;
}
virtual void sorting() = 0;
};
class Bubble : public Sort {
public:
void sorting() override;
};
void Bubble::sorting() {
bool sorted = false;
for (int pass = 1; (pass < m_size) && (!sorted); ++pass) {
sorted = true; // 이번 패스에서 교환이 없다고 가정
for (int cur = 0; cur < m_size - pass; ++cur) {
if (m_data[cur] > m_data[cur + 1]) {
swap(m_data[cur], m_data[cur + 1]);
sorted = false; // 교환이 발생했으므로 정렬 미완료
}
}
}
}
int main() {
vector<int> data = { 10, 7, 9, 1, 3, 2, 8, 6, 4, 5 };
Bubble bubbleSort;
bubbleSort.InitData(data);
cout << "정렬 전: ";
bubbleSort.printall();
bubbleSort.sorting();
cout << "정렬 후: ";
bubbleSort.printall();
return 0;
}
코드 상세 분석
1. 외부 루프 (Pass 제어)
for (int pass = 1; (pass < m_size) && (!sorted); ++pass)- pass: 현재 패스 번호 (1부터 시작)
- pass < m_size: 최대 n-1번의 패스만 필요
- !sorted: 조기 종료 조건 (이미 정렬되어 있으면 중단)
for (초기화; 기본조건 && 조기종료조건; 증감)
2. 내부 루프 (비교 및 교환)
for (int cur = 0; cur < m_size - pass; ++cur)
- cur: 현재 비교할 원소의 인덱스
- m_size - pass: 이미 정렬된 뒤쪽 원소들 제외
3. 조기 종료 최적화
sorted = true; // 패스 시작 시 정렬됨으로 가정
...
sorted = false; // 교환 발생 시 정렬 미완료로 표시
실행 과정 시뮬레이션
입력 배열: [10, 7, 9, 1, 3, 2, 8, 6, 4, 5]
Pass 1 (9번 비교)
비교 0: [10, 7] → 교환 → [7, 10, 9, 1, 3, 2, 8, 6, 4, 5]
비교 1: [10, 9] → 교환 → [7, 9, 10, 1, 3, 2, 8, 6, 4, 5]
비교 2: [10, 1] → 교환 → [7, 9, 1, 10, 3, 2, 8, 6, 4, 5]
비교 3: [10, 3] → 교환 → [7, 9, 1, 3, 10, 2, 8, 6, 4, 5]
비교 4: [10, 2] → 교환 → [7, 9, 1, 3, 2, 10, 8, 6, 4, 5]
비교 5: [10, 8] → 교환 → [7, 9, 1, 3, 2, 8, 10, 6, 4, 5]
비교 6: [10, 6] → 교환 → [7, 9, 1, 3, 2, 8, 6, 10, 4, 5]
비교 7: [10, 4] → 교환 → [7, 9, 1, 3, 2, 8, 6, 4, 10, 5]
비교 8: [10, 5] → 교환 → [7, 9, 1, 3, 2, 8, 6, 4, 5, 10]
결과: 가장 큰 수 10이 맨 끝으로 이동
Pass 2 (8번 비교)
배열: [7, 9, 1, 3, 2, 8, 6, 4, 5, 10]
...
결과: [7, 1, 3, 2, 8, 6, 4, 5, 9, 10]
시간 복잡도 분석
최악의 경우 (Worst Case)
배열이 역순으로 정렬된 경우
- 비교 횟수:
- Pass 1: n-1번
- Pass 2: n-2번
- ...
- Pass n-1: 1번
- 총합: (n-1) + (n-2) + ... + 1 = n(n-1)/2 = O(n²)
- 교환 횟수: 모든 비교에서 교환 발생 = O(n²)
최선의 경우 (Best Case)
배열이 이미 정렬된 경우
- 비교 횟수: n-1번 (첫 번째 패스에서만)
- 교환 횟수: 0번
- 시간 복잡도: O(n)
평균의 경우 (Average Case)
- 시간 복잡도: O(n²)
- 대략 절반 정도의 원소가 교환됨
공간 복잡도
- O(1): In-place 정렬로 추가 메모리 거의 사용 안함
선택 정렬과의 비교
공통점
- 단계별로 가장 큰(또는 작은) 원소를 찾아서 정렬
- 시간 복잡도 O(n²)
- In-place 정렬
차이점
구분선택 정렬버블 정렬
| 교환 방식 | 가장 큰 원소를 한 번에 올바른 위치로 | 가장 큰 원소가 한 칸씩 이동하며 교환 |
| 교환 횟수 | 각 패스마다 최대 1번 | 각 패스마다 여러 번 |
| 비교 횟수 | O(n²) | O(n²) |
| 실제 성능 | 상대적으로 빠름 | 상대적으로 느림 |
| 최선의 경우 | O(n²) | O(n) |
성능 차이의 원인
선택 정렬:
// 한 패스에서 교환은 최대 1번
int minIndex = findMinIndex(start, end);
if (minIndex != start) {
swap(arr[start], arr[minIndex]); // 1번의 교환
}
버블 정렬:
// 한 패스에서 교환이 여러 번 발생
for (int i = 0; i < n-1; i++) {
if (arr[i] > arr[i+1]) {
swap(arr[i], arr[i+1]); // 여러 번의 교환
}
}
장단점 분석
장점
1. 구현의 단순함
- 이해하기 쉬운 직관적인 알고리즘
- 코드가 짧고 간단함
2. In-place 정렬
- 추가 메모리 공간이 거의 필요 없음
- 메모리 제약이 있는 환경에서 유용
3. 안정 정렬 (Stable)
- 동일한 값을 가진 원소들의 상대적 순서가 보존됨
4. 적응적 (Adaptive)
- 이미 정렬된 데이터에 대해서는 O(n) 시간에 실행
- 거의 정렬된 데이터에서 상대적으로 빠름
5. 조기 종료 가능
- 정렬이 완료되면 즉시 종료할 수 있음
단점
1. 느린 성능
- O(n²) 시간 복잡도로 대용량 데이터에 부적합
- 실제로는 다른 O(n²) 알고리즘보다도 느림
2. 과도한 교환
- 불필요한 교환이 너무 많이 발생
- 교환 연산이 비용이 큰 경우 특히 비효율적
3. 실용성 부족
- 실제 프로젝트에서는 거의 사용되지 않음
- 교육 목적 외에는 권장되지 않음
최적화 버전
1. 기본 최적화 (조기 종료)
void bubbleSortOptimized1(vector<int>& arr) {
int n = arr.size();
bool swapped;
for (int pass = 0; pass < n - 1; pass++) {
swapped = false;
for (int i = 0; i < n - pass - 1; i++) {
if (arr[i] > arr[i + 1]) {
swap(arr[i], arr[i + 1]);
swapped = true;
}
}
// 교환이 없었다면 정렬 완료
if (!swapped) break;
}
}
2. 고급 최적화 (범위 축소)
void bubbleSortOptimized2(vector<int>& arr) {
int n = arr.size();
while (n > 1) {
int newN = 0;
for (int i = 1; i < n; i++) {
if (arr[i-1] > arr[i]) {
swap(arr[i-1], arr[i]);
newN = i; // 마지막 교환 위치 기록
}
}
n = newN; // 다음 패스에서는 이 위치까지만 확인
}
}
3. 칵테일 셰이커 정렬 (양방향 버블 정렬)
void cocktailShakerSort(vector<int>& arr) {
int start = 0;
int end = arr.size() - 1;
bool swapped;
do {
swapped = false;
// 왼쪽에서 오른쪽으로
for (int i = start; i < end; i++) {
if (arr[i] > arr[i + 1]) {
swap(arr[i], arr[i + 1]);
swapped = true;
}
}
end--;
if (!swapped) break;
// 오른쪽에서 왼쪽으로
for (int i = end; i > start; i--) {
if (arr[i] < arr[i - 1]) {
swap(arr[i], arr[i - 1]);
swapped = true;
}
}
start++;
} while (swapped);
}
실제 성능 테스트
테스트 코드
#include <chrono>
#include <random>
#include <algorithm>
void performanceTest(int size) {
// 랜덤 데이터 생성
vector<int> data(size);
random_device rd;
mt19937 gen(rd());
uniform_int_distribution<> dis(1, 10000);
for (int& num : data) {
num = dis(gen);
}
// 버블 정렬 테스트
vector<int> bubbleData = data;
auto start = chrono::high_resolution_clock::now();
Bubble bubbleSort;
bubbleSort.InitData(bubbleData);
bubbleSort.sorting();
auto end = chrono::high_resolution_clock::now();
auto bubbleTime = chrono::duration_cast<chrono::milliseconds>(end - start);
// 내장 정렬과 비교
vector<int> stdData = data;
start = chrono::high_resolution_clock::now();
sort(stdData.begin(), stdData.end());
end = chrono::high_resolution_clock::now();
auto stdTime = chrono::duration_cast<chrono::milliseconds>(end - start);
cout << "크기 " << size << "일 때:" << endl;
cout << "버블 정렬: " << bubbleTime.count() << "ms" << endl;
cout << "표준 정렬: " << stdTime.count() << "ms" << endl;
cout << "성능 차이: " << (bubbleTime.count() / (double)stdTime.count()) << "배" << endl;
cout << endl;
}
int main() {
performanceTest(1000);
performanceTest(5000);
performanceTest(10000);
return 0;
}
예상 결과
데이터 크기버블 정렬표준 정렬 (QuickSort)성능 차이
| 1,000개 | 15ms | 0.1ms | 150배 느림 |
| 5,000개 | 380ms | 0.5ms | 760배 느림 |
| 10,000개 | 1,520ms | 1ms | 1,520배 느림 |
언제 버블 정렬을 사용할까?
사용하기 좋은 경우
1. 교육 목적
- 정렬 알고리즘 학습의 첫 단계
- 알고리즘 개념 이해에 도움
2. 매우 작은 데이터
- 10개 이하의 원소
- 성능 차이가 무시할 만한 수준
3. 거의 정렬된 데이터
- 조기 종료 최적화로 O(n) 성능 가능
- 삽입 정렬이 더 나은 선택이긴 함
4. 메모리 제약이 극심한 환경
- In-place 정렬이 필수인 경우
- 하지만 선택 정렬이 더 나음
사용하지 말아야 할 경우
1. 대용량 데이터
- 1000개 이상의 원소
- 실용적이지 않은 성능
2. 실제 프로덕션 코드
- 더 효율적인 알고리즘들이 존재
- QuickSort, MergeSort, HeapSort 등
3. 성능이 중요한 시스템
- 실시간 시스템
- 대용량 데이터 처리 시스템
정리하자면,
1. 버블 정렬은 가장 기본적인 정렬 알고리즘이지만 실용성은 떨어진다.
2. 시간 복잡도 O(n^2) 이고, 특히 교환 횟수가 많아서 다른 O(n^2) 알고리즘보다 훨씬 성능이 느리다.
3. 선택정렬과 비교시에 같은 복잡도 이지만 성능 더 안좋음.
4. 조기종료 최적화를 통해서 이미 정렬된 데이터는 O(n) 성능을 낼 수 있다.
5. 교육 목적과 매우 작은 데이터를 제외하고는 실제로 사용하지 않는다.
반응형
'Game DevTip > Algorithm' 카테고리의 다른 글
| 5. 삽입정렬에 대해서 (3) | 2025.07.27 |
|---|---|
| 4. 선택정렬과 이중 선택정렬에 대해서 알아보자. (2) | 2025.07.26 |
| 2. Algorithm : 알고리즘에 대해서 (6) | 2025.06.09 |
| 1. Algorithm : 피보나치 수열 & 다이나믹 프로그래밍 (0) | 2025.06.09 |
댓글