[알고리즘] 정렬 - 버블 정렬, O(N^2)

  버블 정렬은 O(N^2) 시간 복잡도의 효율이 좋지 않은 정렬 알고리즘 중 하나이다. 아이디어가 간단하면서도 처음 접했을 때 나름 신선하기 때문에 정렬을 처음 배울 때 많이 배우게 되는 것으로 알고 있다. 그리고 버블 정렬의 경우 어떤 처리를 하면 조금이나마 알고리즘 효율을 개선할 수 있고, 정렬되어 있는 데이터를 처리하는 데 걸리는 시간 복잡도를 O(N)으로 낮출 수 있다. 선택 정렬보단 비교적 효율적으로 개선할 수  있는 정렬 알고리즘이다.

 

    버블 정렬 (Bubble Sort) 개념 소개              

  버블 정렬은 두 인접한 데이터를 순차적으로 비교하면서 부분적으로 정렬하는 방식이다. 데이터 전체에 대해 한 번 순차적으로 정렬을 마치고 나면 최댓값이 가장 마지막으로 정렬된다.

버블 정렬의 첫 사이클을 나타낸 그림

 

  위 그림과 같이 2개씩 차례대로 비교하면서 큰 값이 더 뒤에 오도록 배치하다 보면 가장 큰 값이 가장 오른쪽에 위치하게 된다. 이러한 과정을 1번 거치고 나서 맨 마지막 데이터를 제외한 나머지에 대해 같은 과정을 순차적으로 반복하면서 정렬을 하는 것이 버블 정렬이다.

 

  결국 버블 정렬도 선택 정렬과 동일하게 비교 횟수가 N-1번 부터 1씩 차례대로 줄어드는 방식이므로 (N-1)*N/2회의 비교가 이루어진다. 따라서 (N^2)의 시간복잡도를 지닌 알고리즘이다.

 

  하지만 버블 정렬의 경우 정렬 과정에서 데이터가 정렬되어 있는 지 여부를 확인할 수 있다. 예를 들어 순차적으로 비교하면서 순서가 바뀌어 있으면 swap하는데, 마지막 과정까지 swap이 이루어지지 않는다면 데이터가 이미 정렬되어 있었다는 것을 의미한다. 그러면 모든 과정을 종료하게 된다. 이러한 점에서 처음부터 정렬되어 있는 데이터는 N-1번의 비교만 이루어진다는 사실을 알 수 있다. 즉, 최악의 경우와 평균적인 경우 Θ(N^2) 이지만 정렬된 데이터에 대해서는 이러한 처리를 통해  Θ(N)까지 시간 복잡도를 개선할 수 있다. 코드로 구현할 때에는 bool 타입의 flag를 설정해서 이를 감지할 수 있다.

정렬되어 있는 데이터는 N-1번의 비교를 거치고 종료된다.

 

    C++ 구현              

#include <iostream>

void BubbleSort(int* _arr, int _size)
{
    // 비교횟수를 1씩 감소시킴.
    for (int i = _size-1; i > 0; --i)
    {
        // 스왑이 일어났는지 확인하기 위한 flag
        bool isSwap = false;
        // 2개씩 순차적으로 비교 swap한다.
        for (int j = 0; j < i; ++j)
        {
            // 정렬된 상태가 아니라면
            if (_arr[j] > _arr[j + 1])
            {
                // 스왑
                int temp = _arr[j];
                _arr[j] = _arr[j + 1];
                _arr[j + 1] = temp;

                // 스왑되었다면 flag를 true로 변경
                isSwap = true;
            }
        }

        // 남은 데이터 중 스왑이 일어나지 않았으면 정렬된 상태이므로 종료
        if (!isSwap)
            return;
    }
}

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

    return 0;
}