버블 정렬(Bubble sort)

버블 정렬

버블 정렬은 인접한 두 원소의 크기 비교로 정렬이 진행되는 방법입니다. 여기서의 설명은 오름차순으로 정렬하는 것을 기준으로 진행됩니다. 사실 내림차순 정렬은 비교만 바꾸면 되기 때문에 큰 상관은 없습니다.

기본 버블 정렬

처음부터 끝까지 서로 비교하는 것을 하나의 pass라 부릅시다. 한 번의 pass를 거치면 가장 큰 원소가 오른쪽으로 이동하게 됩니다.

예를 들어 길이가 4인 정수형 배열을 정렬한다고 가정하고, 배열 안의 원소는 random 하게 섞여있다고 합시다.

첫번째 pass가 끝난 후

위처럼 첫 번째 pass가 끝나면 가장 큰 원소인 '4'가 배열의 끝에 위치하게 됩니다. 이와 같은 과정을 반복하면 아래처럼 정렬된 배열을 얻을 수 있습니다.

bubble sort 진행 과정

이를 C++ 코드로 구현하면 아래와 같습니다.

#include <iostream>
using namespace std;

void bubble_sort(int arr[], int n)
{
    /*
    arr: 정렬할 array
    n: arr의 길이
    */
    for (int i = 1; i < n; i++)    // pass 표현
    {
        for (int j = 0; j < n - i; j++)
        {
            if (arr[j] > arr[j + 1])
            {
                swap(arr[j], arr[j + 1]);
            }
        }
    }
}

int main()
{
    int my_arr[10] = {0, 1, 5, 3, 4, 2, 6, 7, 8, 9};
    bubble_sort(my_arr, 10);

    for (int idx = 0; idx < 10; idx++)
    {
        printf("%d ", my_arr[idx]);
    }
    cout << "\n";
    return 0;
}

코드를 보면 정렬하는 과정에서 크기가 같은 원소의 순서는 바뀌지 않음을 볼 수 있습니다. 따라서 이는 stable sorting algorithm이라 할 수 있습니다. 그리고 새로운 공간에 정렬 결과를 저장하는 게 아닌 기존 배열 공간 안에서 정렬이 발생합니다. 따라서 이는 In-place algorithm이라 할 수 있습니다.

버블 정렬의 시간 복잡도와 공간 복잡도

위의 예시를 보면 첫 번째 pass에서는 3번의 비교가 이루어지고, 두 번째 pass에서는 2번, 마지막 pass에서는 1번의 비교가 이루어집니다. 따라서 길이가 4인 배열에서 총 3 + 2 + 1 = 6번의 비교가 발생합니다.

이를 일반화시키면, 길이가 n인 배열에서는 비교 연산이 (n - 1) + (n - 2) + ... + 2 + 1 = n(n - 1) / 2번의 비교가 발생합니다. 즉 이 버블 정렬의 시간 복잡도는 O(n**2)입니다. worst case나 best case 상관없이 시간 복잡도는 동일합니다.

bubble_sort 함수를 보면 배열의 길이와 상관없이 i, j 그리고 swap에서 사용되는 temp 변수만 사용됩니다. 따라서 bubble_sort의 공간 복잡도는 O(1)이라 할 수 있습니다.

개선 사항 1

이 버블 정렬을 그대로 쓰기에는 아쉬운 점이 있습니다. 위의 버블 정렬 코드에 이미 정렬된 배열을 주면 정렬이 되어있어도

n(n - 1) / 2만큼의 비교 연산을 수행합니다. 그렇기 때문에 처음부터 또는 정렬하는 중간에 정렬이 완료가 되면 정렬을 그만둘 수 있게 수정하면 좋을 것 같습니다.

void bubble_sort(int arr[], int n)
{
    /*
    arr: 정렬할 배열
    n: arr의 길이
    */
    for (int i = 1; i < n; i++)
    {
        bool swapped = false;    // swap이 일어났는지 판별하는 flag
        for (int j = 0; j < n - i; j++)
        {
            if (arr[j] > arr[j + 1])
            {
                swap(arr[j], arr[j + 1]);
                swapped = true;
            }
        }

        if (!swapped)    // swapped가 false면 정렬이 다 되었음을 의미
        {
            break;
        }
    }
}

이런 버블 정렬 코드에 정렬된 배열이 들어가면 처음 pass만 진행되고 for문 밖을 빠져나가게 됩니다. 따라서 총 n - 1번의 비교만 발생합니다. best case에 대해 O(n) 만큼의 성능을 기대할 수 있게 됩니다.

개선 사항 2

만약 이런 경우가 있다고 생각해봅시다.

다른 예시의 첫 번째 pass

한 번의 pass를 통해 가장 큰 원소인 '5'를 오른쪽에 보내는 데 성공했습니다. 그럼 다음 pass는 4까지 비교를 해야 합니다. 하지만 우리는 위 그림에서 볼 수 있듯이 4는 이미 정렬됐습니다. 따라서 다음 pass에서 2까지만 비교를 할 수 있다면 조금 더 빠르게 정렬이 될 것이라 기대할 수 있습니다.

void bubble_sort(int arr[], int n)
{
    /*
    arr: 정렬할 배열
    n: arr의 길이
    */
    int last_swapped_idx = n;    // 가장 마지막에 확인한 인덱스, 맨 처음에는 배열의 길이로 초기화
    while (last_swapped_idx > 0)  // 마지막에 확인한 인덱스가 0이라는건 정렬이 다 이루어졌음을 의미
    {
        int swapped_idx = 0;
        for (int i = 0; i < last_swapped_idx - 1; i++)    // 마지막에 확인한 인덱스까지만 for문 진행
        {
            if (arr[i] > arr[i + 1])
            {
                swap(arr[i], arr[i + 1]);
                swapped_idx = i + 1;    // 바뀐 인덱스를 저장
            }
        }
        last_swapped_idx = swapped_idx;
    }
}