データ数が１万じゃ〜ダメだね

C言語でバブルソートのブログラムを書き、データ数１万の並び替えを行ったんだけれど、パソコンの性能が向上しすぎて、データ数が１万くらいだと、エンターキーを押して１秒以内に終わってしまうので、遅さをまったく感じないね。バブルソートの遅さ、効率の悪さを体感するには、どうも、データ数を１０万くらいにしないといけないみたい。

データ数nが１０万になると、データの比較回数、データの交換回数がともに約n²/2=５０億回という膨大な回数になるので、遅さを痛感するよ。「これ、いつになったら終わるんだ」と不安になり、実行を強制終了させてしまったほどだにゃ。
　――コンパイルするとき、速く計算してくれるように、最適化のおまじない「-O3」を唱えると、結構、速い。ただし、ここまで強力なおまじないを唱えると（最適化オプションをつけると）、コンパイラーが高速化のためにありとあらゆることをしてくれるので、書いたプログラムと出来上がったプログラムはまったく別なものになっている可能性がある（笑）――
明日、紹介する予定の基本選択法（Max法などともいう）は、データの比較回数は５０億回でバブルソートと同じなのだけれど、データの交換回数がnオーダーでn²オーダーのバブルソートより速く並び終えることができる。それでも結構時間がかかるので、本当に終わるのかと心配になってしまうほど。

明後日紹介するであろう挿入法だと、基本選択法よりもさらに速く並び替えが終わる。挿入法を改良したシェルソートを使うと、さらに爆速化する。

現在、最も速いと言われるクイックソートまでやるかどうかはいまのところ未定だけどね。
だって、これを使うには再帰処理を理解しないといけない。再帰処理を使わない場合はスタックというデータ構造を理解する必要があるんだもん。それに、このアルゴリズム、整列法を説明するのは、ものすごく厄介だし・・・。文章だけでこれを説明するのは、まず、不可能だね。

いろんな整列アルゴリズムの面白い動画。

上の動画の１番目のやつが基本選択法、２番目が挿入法、３番目の奴がクイックソート。
この動画を見ると、並び替えの早さは、基本選択法＞挿入法＞クイックソートのように見えるけれど、これは並び替えるデータの数が多さがクイックソート＞挿入法＞基本選択法であるからそう見えるのであって、実際の並び替えの早さはクイックソート、挿入法、基本選択法の順になる。たぶん、クイックソートと挿入法ではデータの数のオーダーが少なくとも１桁は違っているはず。下手すると、２桁違うかもしれないにゃ。

コッチの動画↓の方がいいのかもしれいないね。

この動画だと、１番目が基本選択法、２番目がバブルソート、３番目が挿入法。この動画を見ると、並び替えの速さが、挿入法＞基本選択法＞バブルソートの順であることがわかると思うにゃ。

参考までに、C言語で書いたプログラムを以下に示す。

#include <stdio.h>
#define N 100000

void BubbleSort(int *, int);       
void Selection(int *, int);
void Insert(int *, int);

main() {
int a[N]={0};

int i;

for (i=0; i<N; i++)
    a[i]=rand()%100000+1;



BubbleSort(a, N);

// Selection(a, N);

// Insert(a, N);

for (i=0; i < N; i++) {
    printf("%8d",a[i]);
}
printf("\n");

}

//バブルソート
void BubbleSort(int *a, int n) {
int i,j;
int s;

for (i=n-1; i>0; i--) {
    for (j=0; j < i; j++) {
        if (a[j]>a[j+1]) {
            s = a[j];
            a[j]= a[j+1];
            a[j+1] = s;
        }
    }
}
}

//基本選択法
void Selection(int *a, int n) {
int i, j, i_max;
int s;

for (i=n-1; i>0; i--) {
    i_max = 0;
    for (j=1; j <= i; j++)  {
        if (a[j] > a[i_max]) i_max=j;
    }
    if (i_max != i) {
        s = a[i];
        a[i]= a[i_max];
        a[i_max] = s;
        }
    }
}

//挿入法
void Insert(int *a, int n) {
int i, j;
int t;

for (i=1; i<n; i++) {
    t=a[i];
    for(j=i-1; j>=0 && a[j]>t; j--)
        a[j+1]=a[j];
    a[j+1]=t;
}
}

正しく並び替えてくれるから、たぶん、プログラムは間違っていないと思う。

ネムネコは、ペンギンOSを使っているので、gccというCコンパイラーでコンパイルした。
だけど、お前らのほとんどはM社の窓OSだから、M社のVisual Cとか、BorlandのCコンパイラーを使うことになるわな〜。窓OSのCコンパイラーで作った実行プログラムはEXEファイルが大きくなるし、なんたって、実行速度が死ぬほど遅い！！
この点はくれぐれも留意するにゃ。
だから、Windows版のgccをインストールしたほうがいいかもしれないにゃ。

https://qiita.com/yut-nagase/items/9bb65481685f6b8002de

M社の窓OSなんてダメダメ、クソOSをいまだに使っている奴の気がしれないにゃ。