ソートアルゴリズムおさらい

温泉でプログラミングしてたら
頭のなかに引っかかったことがあったので
ソートアルゴリズムのおさらいをした。

# バブルソート O (N^2) 安定

void bubble_sort() {
    int i, k, tmp;
    bool changed = false;
    k = 0;
    do {
        changed = false;
        for (int i = 0; i < MAX-1-k; i++) {
            if (array[i] > array[i+1]) {
                tmp = array[i];
                array[i] = array[i+1];
                array[i+1] = tmp;
                changed = true;
            }
        }
        k++;
    } while (changed);
}

# クイックソート O (N^2) ~ O (N log N) 不安定

void quick_sort(int bottom, int top,int data[]) {
    if (bottom >= top)
        return;
    int div = data[bottom];
    int lower = bottom;
    int upper = top;
    int temp;
    while (lower < upper) {
        while (lower <= upper && data[lower] <= div)
            lower += 1;
        while (lower <= upper && data[upper] > div)
            upper -=1;
        if (lower < upper) {
            temp = data[lower];
            data[lower] = data[upper];
            data[upper] = temp;
        }
    }
    temp = data[bottom];
    data[bottom] = data[upper];
    data[upper] = temp;
    quick_sort(bottom, upper-1, data);
    quick_sort(upper+1, top, data);
}

# 単純挿入ソート O (N^2) 安定

void insert_sort(int *array) {
    int i, sorted, temp, insert;
    for (sorted = 0; sorted < MAX - 1; sorted++) {
        insert = array[sorted + 1];
        for (i = 0; i <= sorted; i++) {
            if (array[i] > insert)
                break;
        }
        while (i <= sorted + 1) {
            temp = insert;
            insert = array[i];
            array[i] = temp;
            i++;
        }
    }
}

# コームソート O (N log N) 不安定

void comb_sort(int *array) {
    int i, tmp, sorted, gap;
    gap = N;
    do {
        gap = (gap * 10) / 13;
        if (gap == 0)
            gap = 1;
        
        sorted = true;
        for (i = 0; i < N - gap; i++) {
            if (array[i] > array[i + gap]) {
                sorted = false;
                tmp = array[i];
                array[i] = array[i + gap];
                array[i + gap] = tmp;
            }
        }
    } while((gap > 1) || !sorted);
}

# マージソート O (N log N) 安定

void merge_sort(int n, int* data, int offset) {
    if (n < 2)
        return;
    int i, j, k;
    int m = n/2;
    merge_sort(m, data, offset);
    merge_sort(n-m, data, offset+m);
    int buf[m];
    for (i = 0; i < m; i++)
        buf[i] = data[offset+i];
    j = m;
    i = k = 0;
    while (i < m && j < n) {
        if (buf[i] <= data[offset+j]) {
            data[offset+k] = buf[i];
            i++;
        } else {
            data[offset+k] = data[offset+j];
            j++;
        }
        k++;
    }
    while (i < m) {
        data[offset+k] = buf[i];
        k++;
        i++;
    }
}

あとはここの辺りを頼りにもう少し遊ぶ調べるか