アルゴリズムとデータ構造：バブルソート

プログラマーとしてもう1STEP進むために
自分がよく理解できていない、データ構造とアルゴリズムの勉強を始めました。
実務でいつ使うの？と聞かれても納得してもらえる説明ができるようにしたいと思います。

この本が良さげだったのでそれに沿って進めます。

プログラミングの宝箱 アルゴリズムとデータ構造 第2版

それでは1章のソートから。

まず最初に出て来たのはバブルソート。

名前の由来は泡が水面に上がっていくように、

大きな数から順に整理されて行くところからきているそうです。

bubble_sort.c

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

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

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

void BubbleSort(void);
void output(void);

void BubbleSort(void){
    time_t t;
    printf("Start:%ld\n",time(&t));
    int i, j, flag, k = 0;
    do {
        flag = 0;  
        for(i = 0; i < N - 1 - k; i++){
            if(sort[i] > sort[i + 1]){
                flag = 1;  
                j = sort[i];
                sort[i] = sort[i + 1]; 
                sort[i + 1] = j;
                output();
            }
            ++cnt;
        }
        ++k;
    } while(flag == 1); 
    printf("End:%ld\n",time(&t));
}

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

    printf("Standby.....\n");
    for(i = 0; i < N; i++){
        sort[i] = rand() % 10; 
    }   

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

    BubbleSort();

    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個のデータ数で確認。

$ ./bubble_sort
Standby.....
Before => 7,2,7,3,7,7,9,9,5,4,
Start:1322660011
2,7,7,3,7,7,9,9,5,4,
2,7,3,7,7,7,9,9,5,4,
2,7,3,7,7,7,9,5,9,4,
2,7,3,7,7,7,9,5,4,9,
2,3,7,7,7,7,9,5,4,9,
2,3,7,7,7,7,5,9,4,9,
2,3,7,7,7,7,5,4,9,9,
2,3,7,7,7,5,7,4,9,9,
2,3,7,7,7,5,4,7,9,9,
2,3,7,7,5,7,4,7,9,9,
2,3,7,7,5,4,7,7,9,9,
2,3,7,5,7,4,7,7,9,9,
2,3,7,5,4,7,7,7,9,9,
2,3,5,7,4,7,7,7,9,9,
2,3,5,4,7,7,7,7,9,9,
2,3,4,5,7,7,7,7,9,9,
End:1322660011
After => 2,3,4,5,7,7,7,7,9,9,
Count:44

計算回数が多い、らしい。
なんとなくバカっぽいけど、
他のソートを試してないとそこは実感できないですよね。
データ件数表すをNを1万以上にすると
結果が返らなくなりました。
とりあえず1万で実行。
データの整理経過のoutput()をコメントアウトしてロギングをせず、
乱数も10未満という制限を外し、（10未満の数で1万件でも時間があまりかからなくて、動いてる感がしなかったので）
Nを10000に設定して実行。

$ ./bubble_sort
Standby.....
Before => 
Start:1322660666
End:1322660667
After => 
Count:49993725

この方法じゃあ更に大量のデータは処理しきれないので
もっと効率のいい方法はないか？
ということで次回超有名クイックソートに続きます。