인접한 두 원소를 비교해 큰 값을 뒤로 밀어내는 버블 정렬을 막대 애니메이션으로 확인하세요. 비교·교환 횟수 카운터와 의사코드 하이라이트로 O(n²)이 왜 느린지 직접 볼 수 있습니다.
알고리즘
배열
비교
0
교환/쓰기
0
스텝
0/1,722
읽기
0
보조 메모리
0
재귀 깊이
1/1
재생 속도를 늦추고 '한 단계'로 따라가며 의사코드 하이라이트와 막대 색을 비교해 보세요.
의사코드
for i ← 0 to n−1
for j ← 0 to n−i−2
if a[j] > a[j+1]
swap a[j] ↔ a[j+1]
// a[n−1−i] 확정
시간 복잡도
| 최선 | O(n) |
|---|---|
| 평균 | O(n²) |
| 최악 | O(n²) |
| 공간 | O(1) |
| 안정 | O |
버블 정렬은 배열의 앞에서부터 이웃한 두 원소를 비교해, 왼쪽이 더 크면 자리를 바꾸는 과정을 반복하는 알고리즘입니다. 한 번의 순회가 끝날 때마다 가장 큰 값이 맨 뒤로 '거품처럼' 밀려 올라가기 때문에 버블(bubble)이라는 이름이 붙었습니다.
비교는 (n−1)+(n−2)+…+1번 이루어져 약 n²/2번이 필요하고, 교환도 최악의 경우 비슷한 횟수가 발생해 평균 시간 복잡도는 O(n²)입니다. 대신 이미 정렬된 배열에서는 한 순회에 교환이 없으면 바로 끝낼 수 있어 최선 O(n)이 나옵니다. 같은 값의 상대 순서가 유지되는 안정 정렬이라는 점도 특징입니다.
실무에서는 거의 쓰이지 않지만, '왜 이중 반복이 느린가'를 가장 직관적으로 보여주는 알고리즘이라 교육용으로는 표준입니다. 위의 '거의 정렬됨' 배열로 실행해 보면 역순 배열과 비교 횟수는 같아도 교환 횟수가 확 줄어드는 것을 확인할 수 있습니다. 정렬 알고리즘 시각화에서 다른 알고리즘과 같은 배열로 비교해 보세요.