이웃한 두 값을 비교해서 순서가 틀리면 바꾸는 일을 반복합니다. 큰 값이 거품처럼 한 칸씩 떠올라 오른쪽 끝에 쌓입니다.

버블 정렬 과정을 막대로 보여 주는 시뮬레이터

[자동 재생]을 누르거나 [다음 단계]로 한 단계씩 넘겨 보세요. 슬라이더를 끌면 원하는 단계로 바로 이동합니다. [거의 정렬됨]을 고르면 일찍 끝나는 모습을 볼 수 있습니다.

최선O(n)

평균O(n²)

최악O(n²)

추가 공간O(1)

안정 정렬예

최대 비교n(n−1)/2

한 바퀴마다 가장 큰 값 하나가 확정됩니다

한 바퀴를 도는 동안 큰 값은 비교할 때마다 오른쪽으로 끌려가므로, 바퀴가 끝나면 남은 구간에서 가장 큰 값이 맨 끝에 놓입니다. 다음 바퀴는 그 자리를 빼고 한 칸 짧은 구간만 보면 됩니다. 한 바퀴 동안 교환이 한 번도 없으면 이미 정렬된 것이므로 바로 멈춥니다. 이 조기 종료 덕분에 정렬된 입력에서는 O(n)에 끝납니다.

코테에서는: 교환 횟수 = 역순 쌍의 수

i < j인데 a[i] > a[j]인 쌍을 역순 쌍이라고 합니다. 버블 정렬은 한 번 바꿀 때마다 역순 쌍을 정확히 하나씩 없애므로, 교환 횟수는 역순 쌍의 수와 같습니다. "버블 정렬로 몇 번 바꾸는가"를 묻는 문제에서 n이 크면 직접 시뮬레이션하지 말고, 병합 정렬로 역순 쌍을 O(n log n)에 세야 합니다.