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

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をいまだに使っている奴の気がしれないにゃ。

バブルソート（泡立ち法）

バブルソート（泡立ち法）

 

いま仮に次のような数の列があるとする。

　　

これを小さい数から大きい数へならぶ順（昇順）の数の列に変えたいとする。

この最もシンプルな方法は、隣り合う要素の大小関係を比較し、大小が逆転していたら、隣り合う２つの要素を交換するという方法。

具体的には、まず、｛３,2,1｝の（3,2）を比較する。３と２の大小関係が逆転しているので、３と２を交換し(2,3)にする。すると、

　　

になる。

次に、｛２,3,１｝の（3,1）の大小関係を比較すると、順序が逆転しているので、３と１を交換し、（1,3）にする。

すると、

　　

になる。

これで、最も大きい３を右端に並べられことができた。

 

ということで、｛２,1,３｝の部分列、部分集合

　　

の要素を昇順に並べ替えればいいだろう。

（２,1）を比較すると、これは順序が逆転しているので順序を交換し、（1,2）にすると、

　　

になる。

以上のことをまとめると、

　　

と、隣り合う要素の大小関係を比較し、順序が逆転していたら両者を交換することによって、｛３,２,１｝を昇順に｛１,２,3｝にできる。

こういう数の列の並び替えをバブルソート（泡立ち法）という。

 

では、もっと複雑な

　　

の場合について考える。

(4,2)は順序が逆転しているので、２つの要素を交換すると、

　　

になる。

次に、（４,５）を比較すると、この順序は逆転していないので、交換せずにそのまま。

　　

次に、（５,1）を比較すると、順序が逆転しているので、交換する。

　　

次に、（５,３）を比較すると、順序が逆転しているので、２つの要素を交換する。

　　

これで最も大きな５が右端に並べられた。

というわけで、今度は、

　　

を同様に昇順に並べ替えればよい。

　　{2,4,1,3}→{2,4,1,3}→{2,1,4,3}→{2,1,3,4}

これで、最大の４を右端に持ってくることができたので、４を取り除いた部分集合

　　{2,1,3}

を同様に並び替えると、

　　{2,1,3}→{1,2,3}→{1,2,3}

になる。

これですべて昇順に並び替えることができたのだけれど、{1,2,3}の最大値３を取り除いた部分集合

　　{1,2}

を昇順に並び替える。

　　{1,2}→{1,2}

これで並び替えの作業はおしまい。

これで、{2,4,5,1,3}を昇順に{1,2,3,4,5}と並び替えることができた。

 

さらに一般的につぎのような数の列、集合があるとする。

　　

これを昇順に並び替える方法、アルゴリズムは次のようなものになるだろう。

 

do i=n、n−1,n−2、・・・,2

　do j=1,2,・・・,i−1

　　a(j)とa(j+1)の大小を比較してa(j)とa(j+1)を交換

　end do j

end do i

 

フォートラン的な記述ですが・・・。

 

これを元にFortranのプログラムを作ると、次のようになる。

 

! バブルソート
parameter(n=5)
integer a(n)
integer dummy

a(1)=4; a(2)=2; a(3) = 5; a(4)=1; a(5)=3

do i=n, 2, -1
    do j=1,i-1
        if (a(j).gt.a(j+1)) then !順序が逆転していたら交換
            dummy = a(j)
            a(j)=a(j+1)
            a(j+1)=dummy
        end if
    end do
end do

write(*,*) a

end

 

バブルソートを用いると、昇順にデータを並び替えられるのですが、この方法は、データの比較・交換の回数が最悪、

　　

約n²/2回。

n=100ならば最悪5000回、n=1000ならば５０万回、n=1万ならば５千万回と、データの数nが大きくなると、データの比較・交換回数が大きくなりすぎるので、実際の並び替え、ソーティングでバブルソートが使われることはない。

 

まぁ、パソコンといえども、現在は処理速度、計算速度がトンデモなく速いから、データ数が１万くらいあってもバブルソートですぐに並び終えるので、データ数が１万くらいまでならば、最も基本的なバブルソートで十分に実用に足りると思うけれど、コンピュータの能力が低かったときは、バブルソートの遅さは致命的だったんだケロよ。

 

次回は、バブルソートよりも少しだけ早くソーティングが可能になる方法を紹介するにゃ。