버블 정렬 (Bubble Sort)

인접한 두 원소를 비교해 큰 값을 뒤로 밀어내는 버블 정렬을 막대 애니메이션으로 확인하세요. 비교·교환 횟수 카운터와 의사코드 하이라이트로 O(n²)이 왜 느린지 직접 볼 수 있습니다.

알고리즘

배열

크기48
비교 중교환/쓰기피벗/기준읽기정렬 확정
속도50×

비교

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)이 나옵니다. 같은 값의 상대 순서가 유지되는 안정 정렬이라는 점도 특징입니다.

실무에서는 거의 쓰이지 않지만, '왜 이중 반복이 느린가'를 가장 직관적으로 보여주는 알고리즘이라 교육용으로는 표준입니다. 위의 '거의 정렬됨' 배열로 실행해 보면 역순 배열과 비교 횟수는 같아도 교환 횟수가 확 줄어드는 것을 확인할 수 있습니다. 정렬 알고리즘 시각화에서 다른 알고리즘과 같은 배열로 비교해 보세요.

자주 묻는 질문

버블 정렬은 언제 쓰나요?
실무에서는 성능 때문에 잘 쓰지 않습니다. 다만 배열이 거의 정렬된 상태면 조기 종료로 O(n)에 가깝게 동작하고, 구현이 짧아 작은 데이터나 학습용으로는 의미가 있습니다.
버블 정렬의 최적화 방법이 있나요?
한 순회에서 교환이 한 번도 없으면 정렬이 끝난 것이므로 바로 종료하는 플래그 최적화가 대표적입니다. 마지막으로 교환이 일어난 위치까지만 다음 순회를 제한하는 방법도 있습니다.
버블 정렬은 안정 정렬인가요?
네. 같은 값끼리는 교환하지 않기 때문에 원래 순서가 유지되는 안정 정렬입니다. '중복 많음' 배열 프리셋으로 실행하면 같은 높이의 막대가 순서대로 정렬되는 것을 볼 수 있습니다.

다른 알고리즘 보기