パソコン日記

気づいたこと まとめてみる

C言語でバブルソートの実行時間を測る

ソートの実行時間を測る

以前の記事でプログラムの実行時間の測り方をご紹介いたしました。

1-compinfo.hatenablog.com

今回はバブルソートの実行時間を測定してみたいと思います。

バブルソートとは

バブルソート - Wikipedia

バブルソートwikipediaにあるように、ソートのアルゴリズムの一つで、隣り合う要素を比較しながらソートします。また、アルゴリズムが単純でプログラミングの学習によく用いられているそうです。

ソートの準備

バブルソートのプログラムを作る前に、ソートする配列を作らなければなりません。そこで、要素数Nのランダムな整数型の配列を生成するプログラムを作成しました。

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

int main(void) {
    int i;
    int N = 100;
    int n[N];

    srand(time(NULL));
    for(i=0; i<N; i++){
        n[i] = rand() % 10000;
    }
}

これで生成されるランダムな配列に対してソートを行ってみたいと思います。

マージソートのプログラム

マージソートのプログラムを次のように作ってみました。

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

int main(void) {
    int i,j,t;
    int N = 10;
    int n[N];

    // ランダムな配列を生成
    srand(time(NULL));
    for(i=0; i<N; i++){
        n[i] = rand() % 10000;
    }

    // 配列を表示
    printf("ソート前: ");
    for(i=0; i<N; i++){
        printf("%d ",n[i]);
    }
    printf("\n");

    // バブルソート
    for(i=0; i<N-1; i++){
        for(j=i+1; j<N; j++) {
            if(n[j] < n[i]){
                t = n[j];
                n[j] = n[i];
                n[i] = t;
            }
        }
    }

    // 配列を表示
    printf("ソート後: ");
    for(i=0; i<N; i++){
        printf("%d ",n[i]);
    }
    printf("\n");
}

とりあえず確認のため要素数Nを10で実行してみると次の結果が得られました。

ソート前: 3362 5885 7590 2004 2490 2836 6035 697 7675 5956
ソート後: 697 2004 2490 2836 3362 5885 5956 6035 7590 7675

きちんとソートされているのが確認できました。

マージソートの実行時間を測る

プログラムを次のように変更し、マージソートの実行時間を測ってみました。

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

int main(void) {
    int i,j,t;
    int N = 10000;
    int n[N];
    clock_t start, end;

    // ランダムな配列を生成
    srand(time(NULL));
    for(i=0; i<N; i++){
        n[i] = rand() % 10000;
    }

    // バブルソート
    start = clock();
    for(i=0; i<N-1; i++){
        for(j=i+1; j<N; j++) {
            if(n[j] < n[i]){
                t = n[j];
                n[j] = n[i];
                n[i] = t;
            }
        }
    }
    end = clock();

    printf("要素数: %d\n", N);
    printf("バブルソート実行時間: %f sec\n", (double)(end-start)/CLOCKS_PER_SEC);

}

これをコンパイルして実行すると、大体0.33秒あたりとなりました。この値は使っているコンピュータに依存してくると思います。 また、生成される配列は毎回異るので、実行するごとに実行時間が異なってしまいます。 要素数を増やしていくとどのような、相関があるのか気になったため、何回か実行した平均値をとって見たいと思います。 プログラムを次のようにしてみました。

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

int main(void) {
    int i,j,k,t;
    int N = 10000; //配列の要素数
    int M = 10; //実行回数
    int n[N];
    clock_t start, end;
    double total = 0.0; //各実行時間の和
    struct timeval tv;

    for(k=0; k<M; k++){
        // ランダムな配列を生成
        gettimeofday(&tv,NULL);
        srand(tv.tv_sec * tv.tv_usec);
        for(i=0; i<N; i++){
            n[i] = rand() % 10000;
        }

        // バブルソート
        start = clock();
        for(i=0; i<N-1; i++){
            for(j=i+1; j<N; j++) {
                if(n[j] < n[i]){
                    t = n[j];
                    n[j] = n[i];
                    n[i] = t;
                }
            }
        }
        end = clock();
        total += (double)(end-start)/CLOCKS_PER_SEC;
    }

    printf("要素数: %d\n", N);
    printf("実行回数: %d\n", M);
    printf("バブルソート平均実行時間: %f sec\n", total/M);

}

ランダムな配列を生成するときに、乱数の種の生成はsrand(time(NULL))を使っていました。 しかし、これでは乱数の種は秒単位で変わるので、今回のプログラムには適していません。 そこで、更に細かい時間で乱数の種を生成できるように、上記のようにしてみました。 さらに、バブルソートの実行回数は10回としており、収束が悪いですが、時間の都合上これで行い、 有効数字を2桁でとってみます。 自分のノートパソコンでの結果は次の通りになりました。(データはかなり雑です)

配列の要素数 : 平均の実行時間(秒)
1000 : 0.0027
10000 : 0.35
100000 : 20

素数増えると実行時間結構かかりました。図でも書こうかと思いましたけどやめました。