버블 정렬 (Bubble Sort)
정렬 방식 설명
정렬 순서 (오름차순 기준)
- 배열의 0번째 값부터 인접한 두 값을 비교
- 앞의 값이 뒤의 값보다 크면 자리 교환
- 이 과정을 배열 끝까지 반복하면 가장 큰 값이 맨 뒤로 이동
- 위 과정을 배열 크기 - 1만큼 반복
예시
초기 배열: 5 2 4 1
1회전
- 5 > 2 →
2 5 4 1 - 5 > 4 →
2 4 5 1 - 5 > 1 →
2 4 1 5
2회전
- 2 < 4 → ok
- 4 > 1 →
2 1 4 5
3회전
- 2 > 1 →
1 2 4 5
정렬 완료: 1 2 4 5
기본 코드 (C 언어)
void bubble_sort(int arr[], int n) {
int temp;
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}최적화된 코드
이미 정렬된 상태에서는 불필요한 비교를 생략할 수 있음.
void bubble_sort(int arr[], int n) {
int temp, swapped;
for (int i = 0; i < n - 1; i++) {
swapped = 0;
for (int j = 0; j < n - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = 1;
}
}
if (!swapped) break;
}
}시간 복잡도
| 케이스 | 비교 횟수 | 시간 복잡도 |
|---|---|---|
| 최악 | O(n²) | 대부분의 경우 |
| 평균 | O(n²) | |
| 최선 | O(n) | 이미 정렬된 경우 (최적화 적용 시) |
장단점
장점
- 구현이 매우 간단하다
단점
- 비효율적이며 느림
- 실무에서는 거의 사용하지 않음