버블 정렬은 가장 직관적이고 이해하기 쉬운 정렬 알고리즘 중 하나이다. 인접한 두 원소를 비교하여 순서가 잘못되어 있으면 위치를 교환하는 방식으로 동작한다. 구현이 간단하지만 성능은 O(n²)으로 효율적이지 않다.
동작 원리
배열 [4, 2, 3, 1]을 오름차순으로 정렬하는 과정을 살펴보자
1단계: 첫 번째 패스 (가장 큰 수 정렬)
[4, 2, 3, 1] ← 초기 상태 4와 2 비교 → 4 > 2이므로 교환 [2, 4, 3, 1] 4와 3 비교 → 4 > 3이므로 교환 [2, 3, 4, 1] 4와 1 비교 → 4 > 1이므로 교환 [2, 3, 1, 4] ← 4가 올바른 위치에 정렬됨
2단계: 두 번째 패스 (두 번째로 큰 수 정렬)
[2, 3, 1, | 4] ← 4는 이미 정렬됨 (범위에서 제외) 2와 3 비교 → 2 < 3이므로 교환하지 않음 [2, 3, 1, | 4] 3과 1 비교 → 3 > 1이므로 교환 [2, 1, 3, | 4] ← 3이 올바른 위치에 정렬됨
3단계: 세 번째 패스 (세 번째로 큰 수 정렬)
[2, 1, | 3, 4] ← 3, 4는 이미 정렬됨 2와 1 비교 → 2 > 1이므로 교환 [1, 2, | 3, 4] ← 2가 올바른 위치에 정렬됨
최종 결과
[1, 2, 3, 4] ← 정렬 완료
시각적 다이어그램
패스 1: 가장 큰 원소(4)를 맨 끝으로
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
[4 2 3 1]
↓↗ 4 > 2 ⇒ 교환
[2 4 3 1]
↓↗ 4 > 3 ⇒ 교환
[2 3 4 1]
↓↗ 4 > 1 ⇒ 교환
[2 3 1 4] ✓
패스 2: 두 번째로 큰 원소(3)를 정렬
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
[2 3 1 |4]
↓ ↓ 2 < 3 ⇒ 유지
[2 3 1 |4]
↓↗ 3 > 1 ⇒ 교환
[2 1 3 |4] ✓
패스 3: 세 번째로 큰 원소(2)를 정렬
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
[2 1 |3 4]
↓↗ 2 > 1 ⇒ 교환
[1 2 |3 4] ✓
정렬 완료
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
[1 2 3 4]
Java로 구현
public class BubbleSort {
/**
* 버블 정렬 알고리즘
* @param arr 정렬할 배열
*/
public static void bubbleSort(int[] arr) {
// 외부 루프: 정렬할 패스 횟수 (n-1번)
for (int i = 0; i < arr.length - 1; i++) {
// 내부 루프: 인접한 원소 비교 및 교환
// 매 패스마다 마지막 i개 원소는 이미 정렬되어 있으므로 제외
for (int j = 0; j < arr.length - 1 - i; j++) {
// 앞의 원소가 뒤의 원소보다 크면 교환
if (arr[j] > arr[j + 1]) {
// 두 원소의 위치를 교환
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
// 배열 출력 메서드
public static void printArray(int[] arr) {
System.out.print("[");
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i]);
if (i < arr.length - 1) {
System.out.print(", ");
}
}
System.out.println("]");
}
// 테스트 메인 메서드
public static void main(String[] args) {
// 정렬되지 않은 배열 선언
int[] arr = {4, 2, 3, 1};
// 정렬 전 배열 출력
System.out.println("정렬 전:");
printArray(arr);
// 버블 정렬 수행
bubbleSort(arr);
// 정렬 후 배열 출력
System.out.println("정렬 후:");
printArray(arr);
}
}
/*
실행 결과
정렬 전:
[4, 2, 3, 1]
정렬 후:
[1, 2, 3, 4]
*/
시간 복잡도 분석
비교 횟수 계산
- 길이 n인 배열에서
- 1번째 패스: (n – 1)번 비교
- 2번째 패스: (n-2)번 비교
- 3번째 패스: (n-3)번 비교
- …
- 마지막 패스: 1번 비교
총 비교 횟수
(n-1) + (n-2) + (n-3) + … + 2 + 1
이는 등차수열의 합 공식으로 계산된다
n(n-1) n² - n
───────── → ────────
2 2
빅오 표기법
- 최고차항만 선택: n²
- 상수 계수 제거: n²
- 시간 복잡도: O(n²)
간단하게 판별하는 방법은 중첩된 for문이 2개이므로 O(n²)
공간 복잡도
- O(1): 추가 메모리를 사용하지 않고 제자리에서 정렬(in-place sorting)
장점
- 구현이 매우 간단하다: 초보자도 쉽게 이해하고 구현 가능 (아마도 상대적으로…)
- 추가 메모리 불필요: 제자리 정렬 (in-place)
- 안정 정렬: 동일한 값의 상대적 순서 유지
단점
- 시간 복잡도 O(n²): 대용량 데이터에는 부적합
- 비효율적인 교환 횟수: 많은 swap 연산 발생
- 이미 정렬된 배열에서도 모든 비교 수행 (최적화 전)
최적화 버전
조기 종료 (early exit)를 추가하여 성능 개선 가능
public static void bubbleSortOptimized(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
boolean swapped = false; // 교환 발생 여부 체크
for (int j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true;
}
}
// 교환이 없었다면 이미 정렬된 상태
if (!swapped) {
break;
}
}
}