파이썬 버블 정렬(Bubble Sort)이란? 원리와 예제로 쉽게 이해하기

버블 정렬(Bubble Sort)은 리스트를 오름차순 또는 내림차순으로 정렬하는 가장 기본적인 알고리즘입니다. 구현이 매우 간단해서 정렬 알고리즘을 처음 배울 때 가장 먼저 접하게 되지만, 효율성은 높지 않은 편입니다. 데이터 양이 적을 때는 무난하게 사용할 수 있지만, 리스트나 배열의 길이가 커질수록 실행 시간이 급격히 늘어납니다. 버블 정렬의 시간 복잡도는 O(n²)입니다.
다만 버블 정렬은 제자리(in-place) 정렬 알고리즘이라는 점에서 장점이 있습니다. 정렬 과정에서 추가적인 메모리를 거의 사용하지 않기 때문에 공간 복잡도 측면에서는 매우 효율적입니다(O(1)). 그러나 퀵 정렬, 병합 정렬처럼 성능이 더 좋은 알고리즘이 많기 때문에 실무에서는 자주 사용되지 않습니다.

버블 정렬의 동작 원리

버블 정렬은 두 개의 for 반복문으로 구현합니다. 바깥쪽 반복문은 리스트 전체를 순회하며, 안쪽 반복문은 바깥쪽 반복이 진행되는 동안 매번 리스트를 처음부터 끝까지 훑습니다.

핵심 연산은 인접한 두 요소를 비교하는 것입니다. 앞의 값이 뒤의 값보다 크면 두 요소의 자리를 서로 교환(swap)하여 작은 값을 앞으로, 큰 값을 뒤로 보냅니다. 바깥쪽 반복문 한 회차가 끝날 때마다 그 회차에서 가장 큰 값이 맨 뒤로 밀려납니다. 첫 번째 회차에서는 최댓값이 마지막 인덱스로, 두 번째 회차에서는 두 번째로 큰 값이 뒤에서 두 번째 인덱스로 이동하는 식입니다. 모든 반복이 끝나면 정렬된 리스트를 얻게 됩니다.

예제를 통해 단계별로 확인해 보겠습니다.

정렬할 리스트

바깥쪽 반복문 1회차

5 > 2 → 두 요소를 교환합니다.

5 > 1 → 두 요소를 교환합니다.

5 > 3 → 두 요소를 교환합니다.

5 > 4 → 두 요소를 교환합니다.

(첫 번째 회차가 끝나면 가장 큰 값인 5가 마지막 인덱스에 도달합니다.)

바깥쪽 반복문 2회차

2 > 1 → 두 요소를 교환합니다.

2 < 3 → 교환이 필요 없습니다.

3 < 5 → 교환이 필요 없습니다.

5 > 4 → 두 요소를 교환합니다.

위 예제에서 리스트는 사실 2회차 만에 정렬이 완료되었습니다. 하지만 기본 구현에서는 교환이 더 이상 발생하지 않아도 바깥쪽 반복문이 남은 횟수를 모두 수행합니다. 입력 상태에 따라 첫 회차에 정렬이 끝나는 경우도 있고, 마지막 회차까지 필요한 경우도 있습니다. 따라서 바깥쪽 반복문은 항상 n번 반복됩니다.

파이썬 구현 코드

def bubble_sort(arr):
    for i in range(len(arr)):
        for j in range(len(arr) - 1):
            if arr[j] > arr[j + 1]:
                temp = arr[j]
                arr[j] = arr[j + 1]
                arr[j + 1] = temp
    return arr

array = [2, 3, 1, 5, 4]
print(bubble_sort(array))

실행 결과

[1, 2, 3, 4, 5]

개선된 버블 정렬: 조기 종료

교환 발생 여부를 저장하는 플래그 변수를 활용하면 불필요한 반복을 줄일 수 있습니다. 한 회차에서 교환이 한 번도 일어나지 않았다면 이미 정렬이 완료된 상태이므로 반복을 중단하면 됩니다. 이렇게 개선하면 이미 정렬된 입력에 대해 최선의 시간 복잡도를 O(n)까지 향상시킬 수 있습니다.

def bubble_sort_optimized(arr):
    for i in range(len(arr)):
        swapped = False
        for j in range(len(arr) - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        if not swapped:
            break
    return arr