위키득계정 ↗
기술

버블 정렬

버블 정렬기술
영문명
Bubble sort
주요 연산
이웃 원소 비교와 교환
최악 시간 복잡도
O(n²)
표준 구현의 성질
제자리 정렬, 안정 정렬
버블 정렬은 이웃한 두 원소를 비교해 순서가 잘못되었으면 교환하는 과정을 반복하는 정렬 알고리즘이다. 오름차순에서는 한 번의 순회로 큰 값이 뒤쪽으로 이동한다.

한 번의 순회

4, 1, 3, 2를 왼쪽부터 비교하면 1, 4, 3, 2에서 1, 3, 4, 2를 거쳐 1, 3, 2, 4가 된다. 가장 큰 4는 맨 뒤에 놓이지만 나머지 부분은 아직 정렬되지 않았다.

범위를 줄여 반복

뒤쪽에 확정된 값을 제외하고 남은 앞부분에 같은 처리를 반복한다. 매번 한 원소 이상이 자리를 찾으므로 필요한 비교 범위를 줄일 수 있다. 한 번의 순회만으로 언제나 정렬이 끝나는 것은 아니다.

교환이 없는 경우

어떤 순회에서 교환이 한 번도 없었다면 모든 이웃 쌍의 순서가 맞으므로 종료할 수 있다. 이런 조기 종료를 넣은 구현은 이미 정렬된 입력에서 한 번의 선형 순회로 끝난다. 이를 최악 시간 복잡도와 혼동하지 않는다.

안정성을 지키는 조건

오름차순에서 앞 값이 뒤 값보다 클 때에만 교환하고 같은 값은 바꾸지 않으면 동일 키의 상대 순서를 유지한다. 간단한 구조이지만 큰 일반 입력에서는 이차 시간 비용이 커서 효율을 따져야 한다.

관련 문서

배열 / 정렬 알고리즘 / 삽입 정렬 / 선택 정렬 / 힙 정렬 / 시간 복잡도 / 병합 정렬 / 퀵 정렬