정렬 (sort) : 버블 정렬 (Bubble sort)

원리

---

인접한 인덱스의 데이터끼리 비교하여 swap을 진행하는 방식입니다. 우선순위가 낮은 데이터를 맨 뒤로 보내는 작업을 데이터의 개수 - 1만큼 수행합니다.

소스 코드 (구현)

---

#include <iostream>
#include <algorithm>
#include <functional>

using namespace std;

template <typename T>
void bubble_sort(T *start, T *end, function<bool(T data1, T data2)> cmp = [](T data1, T data2) { return data1 < data2; })
{
    for (T *pos = start; pos < end - 1; pos++)
    {
        for (T *pos2 = start; pos2 < end - pos + start; pos2++)
        {
            if (cmp(*(pos2 + 1), *pos2))
                swap(*pos2, *(pos2 + 1));
        }
    }
}

int main()
{
    int arr[7] = {78, 4, 6, 51, 7, 81, 14};

    bubble_sort(arr, arr + 6);

    for (const auto r : arr)
    {
        cout << r << ' ';
    }

    return 0;
}

성능

• Big O를 계산할 때에는 보통 '비교 횟수'에 대해서 검사를 진행합니다. 위 코드의 비교 연산은 if문입니다. 반복문만큼 비교 횟수가 일어나므로 \((n - 1) + (n - 2) + (n - 3) +... + 1\) 만큼 비교 연산이 실행됩니다. 이 등차수열의 합은 $\frac {n(n-1)}{2}$입니다. 즉, 버블 정렬의 Big O는 \(O(n^2)\)입니다. best case는 단 한 번의 이동이 일어나지 않으나 worst case는 최악의 성능을 일으킵니다.
• stable sort입니다. (stable sort란 같은 값을 가진 데이터끼리 교환이 일어나지 않은 정렬방식을 뜻합니다. 반대로 교환이 일어나면 unstable sort라고 부릅니다.)