アルゴリズムとデータ構造：クイックソート - デラエモン、カイハツニッキ

[クイックソートのロジック]
1.ある値を基準として、それより大きい値は後ろ、小さい値は前へ移動
2.2つのグループそれぞれでまた適当な値を基準にして大きい値は後ろ、小さい値は前へ移動
3.またそれぞれのグループで同じ様に、1-2を繰り返す
4.グループ分けが出来なくなった時点で終了

[計算量のオーダ]
作業の効率性を比較する指標。

[クイックソートの計算量]
最良：O(N Log N)
最悪：O(N2)
平均：O(N Log N)

[ソースコード：quick_sort.c]

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define N 10 /* データ件数 */

int sort[N]; /* 対象データリスト */
int cnt; /* 交換回数 */

void output(void);
void QuickSort(int bottom, int top, int *data);

void QuickSort(int bottom, int top, int *data){
    int lower, upper, div, temp;
    /* 再帰処理を終了するために必要 */
    if(bottom >= top){
        return ; 
    }   
    /* 先頭の値を適当な値とする */
    div = data[bottom];

    for(lower = bottom, upper = top; lower < upper;){
        /* 閾値より大きい数を持つ配列番号を小さい配列番号から順に検索 */
        while(lower <= upper && data[lower] <= div){
            lower++; 
        }

        /* 閾値より小さい数を持つ配列番号を大きい配列番号から順に検索 */
        while(lower <= upper && data[upper] > div){
            upper--; 
        }
        /* 配列番号が以下の条件に合えば入れ替え発生 */
        if(lower < upper){
            temp = data[lower];
            data[lower] = data[upper];
            data[upper] = temp;
            output();
        }

        ++cnt;
    }   

    /* 最初に選択した値を中央に移動する */
    temp = data[bottom];
    data[bottom] = data[upper];
    data[upper] = temp;
    output();

    /* 配列の先頭まで繰り返す */ 
    QuickSort(bottom, upper - 1, data);

    /* 配列の最後尾まで繰り返す */
    QuickSort(upper +  1, top, data);
}

int main(void){
    int i; 
    time_t t;
    srand((unsigned int) time(NULL));

    printf("Standby...\n");
    for(i = 0; i < N; i++){
        /* 配列にランダムな値を格納 */
        sort[i] = rand() % 10;
    }

    printf("Before => ");
    output();

    printf("Start:%ld\n",time(&t));

    QuickSort(0, N - 1, sort);

    printf("End:%ld\n",time(&t));

    printf("After => ");
    output();

    printf("Count:%d\n",cnt);

    return EXIT_SUCCESS;
}

void output(void){
    int i;
    for(i = 0; i < N; i++){
        printf("%d,",sort[i]);
    }
    printf("\n");
}

データ件数10件、10未満の乱数を発生させて実行結果

$ ./quick_sort 
Standby...
Before => 2,9,0,7,8,0,3,7,1,0,
Start:1322690066
2,0,0,7,8,0,3,7,1,9,
2,0,0,1,8,0,3,7,7,9,
2,0,0,1,0,8,3,7,7,9,
0,0,0,1,2,8,3,7,7,9,
0,0,0,1,2,8,3,7,7,9,
0,0,0,1,2,8,3,7,7,9,
0,0,0,1,2,7,3,7,8,9,
0,0,0,1,2,7,3,7,8,9,
0,0,0,1,2,3,7,7,8,9,
End:1322690066
After => 0,0,0,1,2,3,7,7,8,9,
Count:9

ロギングをコメントアウト、乱数の制限も解除、データ件数を1万件にして実行

$ ./quick_sort
Standby...
Before => Start:1322690264
End:1322690264
After => Count:31519

すごく速いのでもっと件数を増やしてみる。
1000万件でやっと処理時間が1秒を超えた。

$ ./quick_sort
Standby...
Before => Start:1322690412
End:1322690416
After => Count:54921891

改修予定

処理時間をマイクロ秒で出力する
引数をデータ件数にする

C言語の標準関数のqsortは処理系によって異なりますが
おおよそクイックソートで実装されているそうです。

クイックソートは基本的にN Log Nの計算量で効率が良いが
元のデータの並び方が悪いとバブルソートと同じ計算量になってしまう。
確実に効率よくソートする方法はないか？ということで
次回のマージソートに続きます。