[알고리즘] 거품 정렬 - Bubble Sort (Python, Java)

선택 정렬(Slection Sort)과 더불어 대표적인 O(N^2) 정렬 알고리즘인 거품 정렬(Bubble Sort)에 대해서 알아보겠습니다.

알고달레에서 코딩 테스트/인터뷰 준비에 좀 더 특화된 컨텐츠를 만나보세요! 📝

기본 컨셉

거품 정렬은 큰 그림에서 보았을 때 뒤에서 부터 앞으로 정렬을 해나가는 구조를 가지고 있습니다. 즉, 맨 뒷자리에 제일 큰 값을 제일 뒤로 보내고, 제일 큰 값 바로 앞에 두번째로 큰 값을 보냅니다. 이를 위해 배열 내의 값들을 앞뒤로 서로 비교해서 자리를 바꾸는 작업을 지속적으로 수행해야 합니다. 이렇게 큰 값을 계속해서 뒤로 보내는 모습이 마치 방울이 이동하는 것과 같이 보여서 거품 정렬이라는 이름이 붙어졌습니다.

먼저 거품 정렬을 통해 어떻게 가장 큰 값을 맨 뒤로 보내는지에 대해서 알아보겠습니다. 맨 첫번째 값부터 시작해서 다음 값들과 차례로 비교하면서 앞의 값이 더 크면 뒤의 값과 자리를 바꾸면 됩니다.

다음과 같이 1부터 5까지 총 5개의 숫자가 들어있는 배열에 대해서 위 로직을 적용해보겠습니다.

[4, 3, 5, 1, 2]

먼저, 4과 3를 비교합니다. 4가 3보다 크기 때문에 자리를 바꿉니다.

[4, 3, 5, 1, 2]
 ^  ^
4 > 3 => Swap
[3, 4, 5, 1, 2]

그 다음과 4과 5를 비교합니다. 4가 5보다 작기 때문에 자리를 바꿀 필요가 없습니다.

[3, 4, 5, 1, 2]
    ^  ^
4 < 5 => No Swap

그 다음과 5과 1를 비교합니다. 5가 1보다 크기 때문에 자리를 바꿉니다.

[3, 4, 5, 1, 2]
       ^  ^
5 > 1 => Swap
[3, 4, 1, 5, 2]

그 다음과 5과 2를 비교합니다. 5가 2보다 크기 때문에 자리를 바꿉니다.

[3, 4, 1, 5, 2]
          ^  ^
5 > 2 => Swap
[3, 4, 1, 2, 5]
             *

이렇게 맨 처음 값부터 시작해서 계속해서 그 다음 값과 대소를 비교하여 앞의 값이 뒤의 값보다 클 경우 자리를 바꿔주면 결국 제일 큰 값을 맨 뒤로 보낼 수가 있습니다.

이 과정을 모든 값으로 확장하면 다음과 같이 두 번째로 큰 값을 제일 큰 값 바로 앞으로 보낼 수 있고, 세 번째로 큰 값을 두 번째로 큰 값 바로 앞으로 보낼 수 있습니다.

Initial: [4, 3, 5, 1, 2]

 Pass 1: [3, 4, 1, 2, 5]
                      *
 Pass 2: [3, 1, 2, 4, 5]
                   *  *
 Pass 3: [1, 2, 3, 4, 5]
                *  *  *
 Pass 4: [1, 2, 3, 4, 5]
             *  *  *  *
 Pass 5: [1, 2, 3, 4, 5]
          *  *  *  *  *

알고리즘 특징

• 거품 정렬은 점점 큰 값들을 뒤에서 부터 앞으로 하나씩 쌓여 나가게 때문에 후반으로 갈수록 정렬 범위가 하나씩 줄어들게 됩니다.
• 왜냐하면, 다음 패스에서는 이전 패스에서 뒤로 보내놓은 가장 큰 값이 있는 위치 전까지만 비교해도 되기 때문입니다.
• 제일 작은 값을 찾아서 맨 앞에 위치시키는 선택 정렬과 비교했을 때 정반대의 정렬 방향을 가집니다.
• 다른 정렬 알고리즘에 비해서 자리 교대(swap)가 빈번하게 일어나는 경향을 가지고 있습니다. 예를 들어, 선택 정렬의 경우 각 패스에서 자리 교대가 딱 한번만 일어납니다.
• 최적화 여지가 많은 알고리즘입니다. 예를 들어, 위 그림에서 Pass 5는 생략할 수 있는 패스입니다. 왜냐하면 Pass 4에서 한 번도 자리 교대가 일어나지 않았기 때문입니다.

복잡도 분석

• 거품 정렬은 별도의 추가 공간을 사용하지 않고 주어진 배열이 차지하고 있는 공간 내에서 값들의 위치만 바꾸기 때문에 O(1)의 공간 복잡도를 가집니다.
• 시간 복잡도는 우선 루프문을 통해 맨 뒤부터 맨 앞까지 모든 인덱스에 접근해야 하기 때문에 기본적으로 O(N)을 시간을 소모하며, 하나의 루프에서는 인접한 값들의 대소 비교 및 자리 교대를 위해서 O(N)을 시간이 필요하게 됩니다. 따라서 거품 정렬은 총 O(N^2)의 시간 복잡도를 가지는 정렬 알고리즘입니다.
• 하지만, 거품 정렬은 부분적으로 정렬되어 있는 배열에 대해서는 최적화를 통해서 성능을 대폭 개선할 수 있으며, 완전히 정렬되어 있는 배열이 들어올 경우, O(N)까지도 시간 복잡도를 향상시킬 수 있습니다.

구현

선택 정렬과 마찬가지로 두 개의 반복문이 필요합니다. 내부 반복문에서는 첫번째 값부터 이전 패스에서 뒤로 보내놓은 값이 있는 위치 전까지 앞뒤 값을 계속해서 비교해나가면서 앞의 값이 뒤의 값보다 클 경우 자리 교대(swap)를 합니다. 외부 반복문에서는 뒤에서 부터 앞으로 정렬 범위를 n-1부터 1까지 줄여나갑니다.

Python 코드

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

Java 코드

public class Bubble {
    public static void sort(int[] arr) {
        for (int i = arr.length - 1; i > 0; i--) {
            for (int j = 0; j <= i; j++) {
                if (arr[j] > arr[j + 1])
                    swap(arr, j, j + 1);
            }
        }
    }

    private static void swap(int[] arr, int a, int b) {
        int tmp = arr[a];
        arr[a] = arr[b];
        arr[b] = tmp;
    }
}

최적화

이전 패스에서 앞뒤 자리 비교(swap)이 한 번도 일어나지 않았다면 정렬되지 않는 값이 하나도 없었다고 간주할 수 있습니다. 따라서 이럴 경우, 이후 패스를 수행하지 않아도 됩니다.

Initial: [1, 2, 3, 5, 4]

 Pass 1: [1, 2, 3, 4, 5] => Swap 있었음
                      *
 Pass 2: [1, 2, 3, 4, 5] => Swap 없었음
                   *  *
=> 이전 패스에서 swap이 한 번도 없었으니 종료

Python 코드

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

Java 코드

public class Bubble {
    public static void sort(int[] arr) {
        for (int i = arr.length - 1; i > 0; i--) {
            boolean swapped = false;
            for (int j = 0; j < i; j++) {
                if (arr[j] > arr[j + 1]) {
                    swap(arr, j, j + 1);
                    swapped = true;
                }
            }
            if (!swapped) break;
        }
    }

    private static void swap(int[] arr, int a, int b) {
        int tmp = arr[a];
        arr[a] = arr[b];
        arr[b] = tmp;
    }
}

추가 최적화

이전 패스에서 앞뒤 자리 비교(swap)가 있었는지 여부를 체크하는 대신 마지막으로 앞뒤 자리 비교가 있었던 index를 기억해두면 다음 패스에서는 그 자리 전까지만 정렬해도 됩니다. 따라서 한 칸씩 정렬 범위를 줄여나가는 대신 한번에 여러 칸씩 정렬 범위를 줄여나갈 수 있습니다.

Initial: [3, 2, 1, 4, 5]

 Pass 1: [2, 1, 3, 4, 5] => 마지막 Swap 위치가 index 1
             ^        *
 Pass 2: [1, 2, 3, 4, 5] => 중간 패스 skip하고 바로 index 1로 보낼 값 찾기
          ^     *  *  *

Python 코드

def bubble_sort(arr):
    end = len(arr) - 1
    while end > 0:
        last_swap = 0
        for i in range(end):
            if arr[i] > arr[i + 1]:
                arr[i], arr[i + 1] = arr[i + 1], arr[i]
                last_swap = i
        end = last_swap

Java 코드

public class Bubble {
    public static void sort(int[] arr) {
        int end = arr.length - 1;
        while (end > 0) {
            int last_swap = 0;
            for (int i = 0; i < end; i++) {
                if (arr[i] > arr[i + 1]) {
                    swap(arr, i, i + 1);
                    last_swap = i;
                }
            }
            end = last_swap;
        }
    }

    private static void swap(int[] arr, int a, int b) {
        int tmp = arr[a];
        arr[a] = arr[b];
        arr[b] = tmp;
    }
}

마치며

지금까지 거품 정렬 알고리즘과 최적화 전략에 대해서 알아보았습니다. 다음 포스팅에서는 삽입 정렬에 대해서 알아보록 하겠습니다.