개념
인접한 두 요소를 비교하여 큰 값을 뒤로 보내는 정렬
가장 큰 값이 거품처럼 뒤로 올라가는 모습
시간복잡도
| 케이스 | 시간복잡도 |
|---|---|
| 최선 | O(n) |
| 평균 | O(n²) |
| 최악 | O(n²) |
| 공간복잡도 | O(1) |
특징
장점
- 구현 간단: 가장 이해하기 쉬운 정렬
- 안정 정렬: 같은 값의 순서 유지
- 제자리 정렬: 추가 메모리 불필요
단점
- 매우 느림: O(n²) 시간복잡도
- 비효율적: 실전에서 거의 사용 안 함
구현 방법
기본 구현
def bubble_sort(arr):
n = len(arr)
for i in range(n):
# 마지막 i개는 이미 정렬됨
for j in range(n - i - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
return arr
# 테스트
print(bubble_sort([64, 34, 25, 12, 22, 11, 90]))
# [11, 12, 22, 25, 34, 64, 90]최적화 버전 (조기 종료)
def bubble_sort_optimized(arr):
n = len(arr)
for i in range(n):
swapped = False
for j in range(n - i - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
swapped = True
# 교환이 없으면 이미 정렬됨
if not swapped:
break
return arr
# 이미 정렬된 경우 O(n)동작 과정
초기: [5, 3, 8, 4, 2]
1회전:
[3, 5, 8, 4, 2] (5, 3 교환)
[3, 5, 8, 4, 2] (5, 8 비교)
[3, 5, 4, 8, 2] (8, 4 교환)
[3, 5, 4, 2, 8] (8, 2 교환) → 8 확정
2회전:
[3, 5, 4, 2, 8]
[3, 4, 5, 2, 8] (5, 4 교환)
[3, 4, 2, 5, 8] (5, 2 교환) → 5 확정
3회전:
[3, 4, 2, 5, 8]
[3, 2, 4, 5, 8] (4, 2 교환) → 4 확정
4회전:
[2, 3, 4, 5, 8] (3, 2 교환) → 3 확정
완료: [2, 3, 4, 5, 8]
템플릿
def bubble_sort_template(arr):
n = len(arr)
# i: 확정된 요소 개수
for i in range(n):
swapped = False
# j: 비교할 인덱스
for j in range(n - i - 1):
# 조건에 맞게 교환
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
swapped = True
# 최적화: 조기 종료
if not swapped:
break
return arr핵심 요약
| 개념 | 설명 |
|---|---|
| 원리 | 인접 요소 비교 및 교환 |
| 시간복잡도 | O(n²) - 최선 O(n) |
| 공간복잡도 | O(1) |
| 안정성 | 안정 정렬 |
다른 정렬과 비교
| 정렬 | 시간복잡도 (평균) | 공간복잡도 | 안정성 |
|---|---|---|---|
| 버블 정렬 | O(n²) | O(1) | 안정 |
| 선택 정렬 | O(n²) | O(1) | 불안정 |
| 삽입 정렬 | O(n²) | O(1) | 안정 |
| 병합 정렬 | O(n log n) | O(n) | 안정 |
| 퀵 정렬 | O(n log n) | O(log n) | 불안정 |
주의사항
1. 사용 시기
# 사용하지 않는 것이 좋음
# 교육용 또는 매우 작은 데이터(n < 10)에만2. 대안
# Python 내장 정렬 사용 (Timsort)
arr.sort() # O(n log n)
sorted(arr)3. 최적화의 한계
# 최적화해도 O(n²)
# 거의 정렬된 경우만 O(n)연습 문제
기초
언제 사용할까?
사용 가능
- 데이터가 매우 적을 때 (n < 10)
- 교육 목적
- 이미 거의 정렬된 경우
사용 불가
- 실전 프로그래밍
- 대용량 데이터
- 성능이 중요한 경우
결론: 실전에서는 사용하지 말 것!