버블 정렬 알고리즘 원리, 코드, 시간 복잡도

쉬운 말로 설명하는 원리

처음 두 요소를 비교합니다. 앞의 것이 더 크면 교환합니다. 그다음 두 번째와 세 번째, 세 번째와 네 번째를 비교하는 식으로 리스트 끝까지 갑니다. 이것이 한 번의 패스입니다. 첫 번째 패스가 끝나면 모든 비교에서 큰 값이 한 칸씩 오른쪽으로 옮겨졌으므로 가장 큰 요소가 맨 끝에 있다는 것이 보장됩니다.

정렬되지 않은 부분에 대해 패스를 반복합니다. 이 부분은 매번 한 요소씩 줄어듭니다. 한 패스에서 교환이 한 번도 일어나지 않으면 리스트가 정렬된 것이므로 일찍 멈출 수 있습니다.

패스별 단계 예제

[5, 1, 4, 2, 8]을 오름차순으로 정렬해 봅시다. 막대 뒤의 요소는 최종 위치에 놓인 것입니다.

조기 종료가 없다면 네 번째 패스를 실행했을 것입니다. 조기 종료가 있으면 여기서는 세 번의 패스면 충분합니다.

파이썬 구현

def bubble_sort(items):
    """Sort a list in place, ascending. Returns the same list."""
    n = len(items)
    for end in range(n - 1, 0, -1):     # last index of the unsorted part
        swapped = False
        for i in range(end):
            if items[i] > items[i + 1]:  # strict >, keeps equal items in order
                items[i], items[i + 1] = items[i + 1], items[i]
                swapped = True
        if not swapped:                  # no swaps: already sorted
            break
    return items
print(bubble_sort([5, 1, 4, 2, 8]))     # [1, 2, 4, 5, 8]
print(bubble_sort([3, 3, 1]))           # [1, 3, 3]
print(bubble_sort([]))                  # []

안쪽 반복문은 end에서 멈춥니다. 그 뒤의 요소는 이미 제자리에 있기 때문입니다. swapped 플래그 덕분에 정렬된 입력에서 최선의 경우가 O(n)이 됩니다.

시간 복잡도와 공간 복잡도

역순으로 놓인 요소가 10,000개라면 비교와 교환이 거의 5,000만 번입니다. 교환 횟수는 항상 역전(inversion), 즉 순서가 틀린 쌍의 개수와 같습니다.

버블 정렬과 다른 정렬 비교

버블 정렬은 인접한 요소만, 그것도 엄밀히 순서가 틀렸을 때만 교환하므로 안정 정렬입니다. 같은 값의 요소는 서로를 추월하지 않습니다. 삽입 정렬은 복잡도와 안정성이 같지만 실제로는 쓰기 횟수가 적고 더 빠릅니다. 그래서 Timsort 같은 하이브리드 알고리즘 내부에는 버블 정렬이 아니라 삽입 정렬이 쓰입니다.

변형과 흔한 실수

• 칵테일 셰이커 정렬은 패스마다 왼쪽에서 오른쪽, 오른쪽에서 왼쪽으로 번갈아 진행합니다. 그러면 끝에 있는 작은 요소(거북이라고 부름)가 더 빨리 앞으로 옵니다. 그래도 O(n²)입니다.
• 콤 정렬은 일정한 간격만큼 떨어진 요소를 비교하면서 간격을 줄여 나가므로 많은 거북이를 일찍 제거합니다. 간격이 1이면 버블 정렬이 됩니다.
• 홀짝 전치 정렬은 홀수 쌍을 모두 비교한 다음 짝수 쌍을 모두 비교하며, 병렬 정렬을 가르칠 때 쓰입니다.

버블 정렬을 쓰는 경우

실제 코드에서는 거의 쓰지 않습니다. 파이썬에서는 sorted(items)나 items.sort()를 호출하세요. 이들은 Timsort를 사용하고, O(n log n)에 동작하며, 안정 정렬입니다. 그래도 버블 정렬은 알아 둘 만합니다. 설명하기 가장 쉬운 정렬이고, 정확성 증명도 따라가기 쉬우며, 반복문, 교환, 복잡도에 대한 면접과 시험의 단골 첫 문제이기 때문입니다.

실질적인 장점은 O(n) 한 번의 패스로 리스트가 정렬되어 있는지 알 수 있다는 것 하나뿐인데, 이웃끼리 비교하는 단순한 반복문으로도 정렬 없이 확인할 수 있습니다.