[Programming/Algorithm] 버블 정렬(Bubble Sort)

버블 정렬은 정렬의 대명사로 알려져 있는 정렬 방법이다. 그만큼 이해하기도 구현하기도 쉽다. 물론 이해와 구현이 쉬운 만큼 성능에는 아쉬움이 있따.

버블 정렬은 인접한 두 개의 데이터를 비교해가면서 정렬을 진행하는 방식이다. 두 데이터를 비교하여, 정렬 순서상 위치가 바뀌어야 하는 경우에 두 데이터의 위치를 바꿔나간다. 

버블이란 이름이 붙은 이유도 앞에서부터 순서대로 비교하고 교환하는 일련의 과정이 거품이 일어나는 모습에 비유되어 버블 정렬이라 이름 지어진 것이다.

#include <iostream>

#define SWAP(a, b) { a ^= b; b ^= a; a ^= b; }

using std::cout;
using std::cin;
using std::endl;


int main() {
    int arr[] = { 5, 4, 1, 3, 6 };
    int len = sizeof(arr) / sizeof(int);

    for (int i = 0; i < len- 1; i++) {
        for (int j = 0; j < (len - i) - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                SWAP(arr[j], arr[j + 1]);
            }
        }
    }

    for (int i = 0; i < len; i++) {
        cout << arr[i] << ' ';
    }
    cout << endl;

    return 0;
}


/* 결과

1 3 4 5 6

*/

---

버블 정렬(Bubble Sort): 성능평가

정렬 알고리즘의 성능은 다음 두 가지를 판단하는 것이 일반적이다. '비교연산'과 데이터의 이동을 위한 '대입연산'이 정렬과정의 핵심연산이기 때문이다.

• 비교의 횟수 : 두 데이터간의 베교연산의 횟수
• 이동의 횟수 : 위치의 변경을 위한 데이터의 이동횟수

실제로 시간 복잡도에 대한 빅-오를 결정하는 기준은 '비교의 횟수'이다. 하지만 '이동의 횟수'까지 살펴보면 동일한 빅-오의 복잡도를 갖는 알고리즘간의 세밀한 비교가 가능하다. 

버블 정렬에서 데이터의 수가 n개일 때 진행이 되는 비교 횟수는 다음과 같다.

(n-1) + (n-2) + ... + 2 + 1

따라서 버블 정렬의 비교연산에 대한 빅-오는 최악의 경우와 최선의 경우 구분 없이 다음과 같다.

O(n의 2제곱)

단순히 보면 반복문이 중첩되어 있을 뿐인데, 이렇듯 실제 활용하기 부담스러운 정도의 성능을 보인다. 그렇다면 데이터의 이동횟수(교환횟수)는 어떨까? 이는 최선의 경우와 최악의 경우가 구분이 된다. 데이터가 이미 정렬되어 있는 상태라면 데이터의 이동이 한 번도 일어나지 않지만, 반대로 정렬기준의 역순으로 저장된 상태라면 비교의 횟수와 이동의 횟수가 일치하기 때문이다. 따라서 데이터 이동연사에 대한 빅-오는 최악의 경우를 기준으로 하여 다음과 같이 판단한다.

O(n의 2제곱)

사실 최악의 경우, 버블 정렬의 데이터 이동횟수는 비교횟수보다 3배 더 많다. 값의 교환 과정에서 대입 연산이 3회 진행되기 때문이다. 하지만 빅-오를 판단하는 과정에서는 이를 무시한다.