[06. 정렬 알고리즘] 버블 정렬

• 정렬 되었는지 확인

#include <iostream>
using namespace std;

bool is_sorted(int arr[], const int N) {
    for (int i = 1; i < N; i++)
        if (arr[i - 1] > arr[i])
            return false;
    return true;
}

• 기본 Bubble정렬

void BubbleSort0(int arr[], const int N) {
    for (int i = 1; i < N; i++)
        for (int j = N - 1; j >= i; j--)
            if (arr[j - 1] > arr[j])
                swap(arr[j - 1], arr[j]);
}

• std::swap() --> swap2() (define 함수) 변경

#define swap2(type, x, y) do { type t = x; x = y; y = t; } while (false)

void BubbleSort1(int arr[], const int N) {
    for (int i = 1; i < N; i++)
        for (int j = N - 1; j >= i; j--)
            if (arr[j - 1] > arr[j])
                swap2(int, arr[j - 1], arr[j]);
}

• 중간에 정렬이 끝났으면 종료

void BubbleSort2(int arr[], const int N) {
    for (int i = 1; i < N; i++) {
        bool exchg = false;
        for (int j = N - 1; j >= i; j--)
            if (arr[j - 1] > arr[j]) {
                swap2(int, arr[j - 1], arr[j]);
                exchg = true;
            }
        if (!exchg)
            break;
    }
}

• 정렬된 부분은 다음에 생략(왼쪽 끝)

void BubbleSort3(int arr[], const int N) {
    int left = 1;
    for (int i = left; i < N; i = left) {
        left = N;
        for (int j = N - 1; j >= i; j--)
            if (arr[j - 1] > arr[j]) {
                swap2(int, arr[j - 1], arr[j]);
                left = j;
            }
    }
}

• 정렬된 부분은 다음에 생략(왼쪽 끝, 오른쪽 끝), 좌우 교대로 정렬

void BubbleSort4(int arr[], const int N) {
    int right = N;
    int left = 1;
    for (int i = left; i < right; i = left) {
        static bool b_toright = true;
        if (b_toright) {
            int last = N;
            for (int j = right - 1; j >= i; j--)
                if (arr[j - 1] > arr[j]) {
                    swap2(int, arr[j - 1], arr[j]);
                    last = j;
                }
            left = last;
        }
        else {
            int last = 0;
            for (int j = i; j < right; j++)
                if (arr[j - 1] > arr[j]) {
                    swap2(int, arr[j - 1], arr[j]);
                    last = j;
                }
            right = last;
        }
        b_toright = !b_toright;
    }
}

• std::swap() 함수를 안쓰면 속도가 훨씬(2배 이상) 빨라진다.
• 1, 2, 3은 차이가 작거나 순위가 변하지만 BubbleSort4는 항상 1등.

int main(int num) {
    const int N = RAND_MAX;
    int arr[N];

    for (int i = 0; i < N; ++i)
        arr[i] = rand();

    int start = clock();
    //BubbleSort0(arr, N);         // 4913, 4698, 4931 ms
    //BubbleSort1(arr, N);         // 2220, 2206, 2013 ms
    //BubbleSort2(arr, N);         // 1852, 1921, 1853 ms
    //BubbleSort3(arr, N);         // 2079, 2118, 2062 ms
    BubbleSort4(arr, N);           // 1577, 1661, 1664 ms
    cout << clock() - start << endl;
    cout << is_sorted(arr, N) << endl;
}