버블 정렬

버블 정렬은 설명하기 가장 쉬운 정렬 알고리즘입니다. 이웃한 두 값을 비교해 순서가 틀리면 교환하고, 이를 반복합니다. 긴 목록에서는 느리지만 모든 단계를 따라가기 쉬워서, 처음 살펴보는 알고리즘으로 가장 널리 쓰입니다.

높이가 다른 막대들이 정렬되는 모습. 이웃한 두 막대가 교환을 위해 강조되어 있고, 가장 높은 막대들은 이미 끝에 자리 잡았다
높이가 다른 막대들이 정렬되는 모습. 이웃한 두 막대가 교환을 위해 강조되어 있고, 가장 높은 막대들은 이미 끝에 자리 잡았다

기본 아이디어

목록을 왼쪽에서 오른쪽으로 훑으며 이웃한 값 쌍을 하나씩 봅니다. 왼쪽 값이 오른쪽 값보다 크면 교환합니다. 끝에 도달하면 거품이 수면으로 떠오르듯 가장 큰 값이 마지막 자리까지 옮겨져 있습니다. 이렇게 한 번 훑는 것을 패스라고 합니다. 목록이 정렬될 때까지 패스를 반복합니다.

예시

5, 1, 4, 2, 8을 봅시다. 첫 패스는 5와 1을 비교해 교환하고, 이어서 5와 4(교환), 5와 2(교환), 5와 8(교환 없음)을 비교합니다: 1, 4, 2, 5, 8. 이제 8은 최종 위치에 있습니다. 두 번째 패스는 1과 4(교환 없음), 4와 2(교환), 4와 5(교환 없음)를 비교합니다: 1, 2, 4, 5, 8. 세 번째 패스에서는 교환이 전혀 없으므로 목록이 정렬된 것입니다. 비교 9번, 교환 4번입니다.

패스마다 값이 하나씩 제자리를 찾는 이유

패스 중에는 지금까지 본 가장 큰 값이 항상 함께 옮겨집니다. 패스가 그 값에 도달하면 이후 비교마다 그 값이 오른쪽으로 한 칸씩 이동합니다. 그래서 첫 패스는 가장 큰 값을 맨 끝에, 두 번째 패스는 두 번째로 큰 값을 그 바로 앞에 놓는 식입니다. k번째 패스가 끝나면 마지막 k자리는 확정되고, 다음 패스는 한 칸 앞에서 멈출 수 있습니다. 그래서 패스가 점점 짧아집니다.

교환 횟수는 역순쌍 개수와 같다

역순쌍은 순서가 잘못된 값 쌍, 즉 큰 값이 작은 값보다 앞에 있는 쌍입니다. 순서가 틀린 이웃한 두 값을 교환하면 역순쌍이 정확히 하나 사라지고 새로 생기지 않습니다. 따라서 비교 순서와 상관없이 버블 정렬의 교환 횟수는 시작 목록의 역순쌍 개수와 정확히 같습니다. 정렬된 목록에는 역순쌍이 없고, 값 n개의 역순 목록에는 가능한 최대인 n(n − 1)/2개가 있습니다.

조기 종료와 비용

패스 전체에서 교환이 없으면 이웃한 값이 모두 순서대로이므로 목록은 정렬된 것입니다. 이를 확인하면 버블 정렬은 정렬된 목록을 n − 1번 비교하는 패스 한 번으로 끝낼 수 있습니다. 최악의 경우에는 여전히 n − 1번의 패스와 n(n − 1)/2번의 비교가 필요하고, 평균 교환 횟수는 n(n − 1)/4번입니다. 둘 다 n²에 비례해 늘어나므로 목록 길이가 두 배가 되면 정렬 시간은 약 네 배가 됩니다.

버블 정렬은 안정 정렬입니다. 같은 값은 교환되지 않으므로 원래 순서를 유지합니다. 추가 메모리 없이 제자리에서 정렬합니다. 삽입 정렬도 같은 특성을 가지면서 보통 단계가 더 적고, 병합 정렬과 퀵 정렬은 n log n에 비례하는 시간이 걸려 긴 목록에서 훨씬 빠릅니다.

직접 해 보기

앱을 열고 ‘재생’을 누르거나, ‘단계’를 눌러 비교를 하나씩 진행하세요. 비교 중인 두 값은 강조 표시되고, 교환은 별도의 색으로 표시되며, 제자리에 놓인 값은 초록색으로 바뀝니다. 역순 목록으로 최악의 경우를, 거의 정렬된 목록으로 조기 종료가 몇 번의 패스 만에 정렬을 끝내는 모습을 확인하거나, 위 예시의 숫자를 입력해 보세요.

자주 묻는 질문

버블 정렬의 시간 복잡도는?

최악과 평균의 경우 O(n²)이며, 값이 n개이면 최대 n(n − 1)/2번 비교합니다. 조기 종료를 쓰면 이미 정렬된 목록은 패스 한 번, 즉 O(n)으로 끝납니다. 추가 메모리는 O(1)만 필요합니다.

버블 정렬은 안정 정렬인가요?

네. 왼쪽 값이 엄밀히 더 클 때만 이웃한 두 값을 교환하므로, 같은 값은 서로 앞지르지 않고 원래 순서를 유지합니다.

버블 정렬과 삽입 정렬의 차이는?

둘 다 이웃한 값을 교환하고, 교환 횟수도 둘 다 역순쌍 개수와 같습니다. 버블 정렬은 정렬되지 않은 부분 전체를 패스로 훑지만, 삽입 정렬은 새 값을 필요한 만큼만 앞쪽으로 옮기므로 보통 비교 횟수가 더 적고, 거의 정렬된 목록에서는 특히 그렇습니다.

버블 정렬은 언제 쓰면 좋나요?

주로 교육용이나, 속도보다 단순함이 중요한 아주 짧은 목록에 적합합니다. 그보다 큰 데이터에는 프로그래밍 언어에 내장된 정렬이 훨씬 빠릅니다.

시도해 볼 준비가 되셨나요?

브라우저에서 PictorX를 엽니다. 설치가 필요 없고 시작하는 데 신용 카드가 필요하지 않습니다.

버블 정렬 해 보기