第53回 『ソートを考える その３』(バブルソートにいたずらをしよう）
前回までは有名なソートのアルゴリズムを説明してきました。芋虫が這うよりはバッタが跳ねる方がソートの効率が良いことをお話しましたが、それではバカソートと呼ばれるくらいに効率の悪いバブルソートにちょっといたずらをしてみましょう。このちょっとしたいたずらでバブルソートがクイックソート程に劇的に高速になってしまうのです。
バブルソートの効率の悪さの最大の問題点は隣どうしとの比較と交換にあります。これは芋虫が這い回ることと同じです。芋虫をバッタにすればもしかすれば速くなるかも知れないというのが、いたずらのきっかけです。
バブルソートは次のプログラムです。
bsort(data,ldata)
int data[];
int ldata;
{
int i,flag,t;
do{
flag=0;
for(i=0;i<ldata;i++){
if(data[i]>data[i+1]){
t =data[i ];
data[i ]=data[i+1];
data[i+1]=t;
flag=1;
}
}
}while(flag);
}
このプログラムでは隣どうしの比較と交換しか行なわないので、これを隣どうしではなく、最初はもっと遠い相手と比較するようにし、徐々にその間隔を小さくしていくように書き直します。
#define GAP_FACTOR 0.5
sort(int *data,int ldata)
{
int i,j,t,gap,flag;
gap=(ldata+1)/2; ー（１）
if(gap==0)gap=1;
while(1){
flag=0;
for(i=0,j=gap;j<=ldata;i++,j++){ ー（２）
if(data[i]>data[j]){
t =data[i];
data[i]=data[j];
data[j]=t;
flag=1;
}
}
if(gap==1){ ー（３）
if(flag)continue;
break;
}
gap=((double)gap)*GAP_FACTOR; ー（４）
if(gap==0)gap=1;
}
}
変更の主なところは、
（１）初期の間隔は配列の要素数の半分とする。
（２）隣どうしではなく、そのときの間隔分離れた要素との比較と交換を行なう。
（３）間隔が１のときには通常のバブルソートと同じなので交換がなくなるまで繰り返します。
（４）間隔の縮小率は 0.5 とします。
このプログラムはシェルソートと非常に似ていますが、（３）の部分がシェルソートの場合は交換が発生したときには配列の先頭に向かって交換がなくなるまで比較を行うのですが、このプログラムは基本的にはバブルソートですのでそのようなことは行ないません。
次にこのプログラムの動作を見てみましょう。要素数が９なので間隔の初期値は４となります。
３８２７６１５４９
↑ ↑
３８２７６１５４９
↑ ↑ 交換
３１２７６８５４９
↑ ↑
３１２７６８５４９
↑ ↑ 交換
３１２４６８５７９
↑ ↑
３１２４６８５７９
次に間隔を半分の２にします。
３１２４６８５７９
↑ ↑ 交換
２１３４６８５７９
↑ ↑
２１３４６８５７９
↑ ↑
２１３４６８５７９
↑ ↑
２１３４６８５７９
↑ ↑ 交換
２１３４５８６７９
↑ ↑ 交換
２１３４５７６８９
↑ ↑
２１３４５７６８９
次に間隔を半分の１にします。
２１３４５７６８９
↑↑ 交換
１２３４５７６８９
↑↑
１２３４５７６８９
↑↑
１２３４５７６８９
↑↑
１２３４５７６８９
↑↑
１２３４５７６８９
↑↑ 交換
１２３４５６７８９
↑↑
１２３４５６７８９
↑↑
１２３４５６７８９
交換があったので再び繰り返しますが、これでソートは完成しています。かなり効率がいいようなので、実際に要素数を１００としてランダムな値を配列に代入して実行してみました。
間隔 比較回数 総比較回数 交換回数 総交換回数
50 50 50 20 20
25 75 125 31 51
12 88 213 42 93
6 94 307 54 147
3 97 404 51 198
1 99 503 72 270
1 99 602 55 325
1 99 701 46 371
1 99 800 39 410
1 99 899 32 442
1 99 998 25 467
1 99 1097 19 486
1 99 1196 17 503
1 99 1295 11 514
1 99 1394 8 522
1 99 1493 5 527
1 99 1592 4 531
1 99 1691 3 534
1 99 1790 3 537
1 99 1889 3 540
1 99 1988 3 543
1 99 2087 3 546
1 99 2186 2 548
1 99 2285 1 549
1 99 2384 0 549
この結果を見てみると、間隔が１のときの繰り返し回数がかなり多いのが気になります。この原因は間隔の縮小率が不適当な感じがするので、この例では 0.5 だった値を0.1 から 0.9 まで 0.1 きざみでそれぞれの総比較回数と総交換回数を表にしてみました。
間隔縮小率 総比較回数 総交換回数
0.1000 6382 1345
0.2000 5782 1099
0.3000 5082 897
0.4000 3982 713
0.5000 2582 505
0.6000 3552 409
0.7000 1146 285
0.8000 1185 237
0.9000 1913 247
この表を見てみると、縮小率が 0.6 から 0.9 の間が最も総比較回数も総交換回数が小さいことが分かります。そこで再び間隔の縮小率を 0.6 から 0.9 の間で 0.02 きざみで実験してみました。
間隔縮小率 総比較回数 総交換回数
0.6000 2562 459
0.6200 2460 415
0.6400 1662 355
0.6600 1359 335
0.6800 1349 309
0.7000 1245 273
0.7200 1038 269
0.7400 1123 269
0.7600 1211 251
0.7800 1198 241
0.8000 1273 247
0.8200 1352 247
0.8400 1431 247
0.8600 1510 229
0.8800 1751 251
この表では、縮小率が 0.7 から 0.8 の間が小さくなっています。いろいろと試してみると平均的に 0.76 から 0.77 の間が最も効率が良さそうです。そこでその中間をとって 0.765 と決めてました。多分もっと多く実験すると最適な縮小率が求められると思います。
このように縮小率で結果が変わってくるのは、ソートの初期の比較間隔の大きいときに配列の要素が最終的に決定されるべき位置の近辺に飛躍するのですが、このちょっとしたズレが最終的に間隔を１となったときに収束させづらくなっていると予想されます。また最初の比較間隔を要素数の半分としましたが、これについてもいろいろと試してみた結果これで良さそうです。
再びそれぞれの比較間隔での比較回数と交換回数を１０万個の要素数で実験してみました。
間隔 比較回数 総比較回数 交換回数 総交換回数
50000 50000 50000 25006 25006
38250 61750 111750 19575 44581
29261 70739 182489 18885 63466
22384 77616 260105 18421 81887
17123 82877 342982 18381 100268
13099 86901 429883 18740 119008
10020 89980 519863 19604 138612
7665 92335 612198 20328 158940
5863 94137 706335 20688 179628
4485 95515 801850 21072 200700
3431 96569 898419 21037 221737
2624 97376 995795 21511 243248
2007 97993 1093788 21609 264857
1535 98465 1192253 21995 286852
1174 98826 1291079 22122 308974
898 99102 1390181 22102 331076
686 99314 1489495 22220 353296
524 99476 1588971 22261 375557
400 99600 1688571 21889 397446
306 99694 1788265 21821 419267
234 99766 1888031 21950 441217
179 99821 1987852 21877 463094
136 99864 2087716 23390 486484
104 99896 2187612 22705 509189
79 99921 2287533 23570 532759
60 99940 2387473 22249 555008
45 99955 2487428 22287 577295
34 99966 2587394 19383 596678
26 99974 2687368 19936 616614
19 99981 2787349 20006 636620
14 99986 2887335 25573 662193
10 99990 2987325 22914 685107
7 99993 3087318 19533 704640
5 99995 3187313 18288 722928
3 99997 3287310 23748 746676
2 99998 3387308 15866 762542
1 99999 3487307 16074 778616
1 99999 3587306 2432 781048
1 99999 3687305 371 781419
1 99999 3787304 118 781537
1 99999 3887303 43 781580
1 99999 3987302 17 781597
1 99999 4087301 7 781604
1 99999 4187300 1 781605
1 99999 4287299 0 781605
この表で分かることは、交換の回数は比較間隔が２以上のときには一定の交換回数なのですが、比較間隔が１のとき、即ち通常のバブルソートになったときには交換回数が極端に減少していることが分かります。ということは比較間隔が２以上のときにほぼ整列していることが推測できます。また比較間隔が１のときには無駄な比較を行なっていることになりますので、比較間隔が１のときにはキャッチアップソートに変更した方が効率がいいことが分かります。
そこで、プログラムを
#define GAP_FACTOR 0.765
sort(int *data,int ldata)
{
int i,j,k,t,gap;
gap=(ldata+1)/2;
if(gap==0)gap=1;
ctot=0;
stot=0;
while(1){
if(gap==1){
for(i=0;i<ldata;i++){
j=i;
k=i+1;
while(j>=0 && data[j]>data[k]){
t =data[j];
data[j]=data[k];
data[k]=t;
j--;
k--;
}
}
break;
}
else{
for(i=0,j=gap;j<=ldata;i++,j++){
if(data[i]>data[j]){
t =data[i];
data[i]=data[j];
data[j]=t;
}
}
}
gap=((double)gap)*GAP_FACTOR;
if(gap==0)gap=1;
}
}
そうすると、
間隔 比較回数 総比較回数 交換回数 総交換回数
76500 23500 23500 11909 11909
58522 41478 64978 13008 24917
44769 55231 120209 13062 37979
34248 65752 185961 13565 51544
26199 73801 259762 14767 66311
20042 79958 339720 16344 82655
15332 84668 424388 17723 100378
11728 88272 512660 18711 119089
8971 91029 603689 19413 138502
6862 93138 696827 19936 158438
5249 94751 791578 20637 179075
4015 95985 887563 20789 199864
3071 96929 984492 21260 221124
2349 97651 1082143 21234 242358
1796 98204 1180347 21703 264061
1373 98627 1278974 21393 285454
1050 98950 1377924 21998 307452
803 99197 1477121 22184 329636
614 99386 1576507 22208 351844
469 99531 1676038 22411 374255
358 99642 1775680 21790 396045
273 99727 1875407 22527 418572
208 99792 1975199 22393 440965
159 99841 2075040 22366 463331
121 99879 2174919 22244 485575
92 99908 2274827 21748 507323
70 99930 2374757 22021 529344
53 99947 2474704 21893 551237
40 99960 2574664 23288 574525
30 99970 2674634 19445 593970
22 99978 2774612 21911 615881
16 99984 2874596 23142 639023
12 99988 2974584 20528 659551
9 99991 3074575 20448 679999
6 99994 3174569 17364 697363
4 99996 3274565 21886 719249
3 99997 3374562 12703 731952
2 99998 3474560 14018 745970
1 110182 3584742 10183 756153
となり、比較間隔が１のときの比較回数と交換回数は殆ど無駄のないように改善されました。
ちなみに、１０万個のランダムな要素をソートしたときの結果は
クイックソート 0.3432 秒
シェル ソート 0.4364 秒
ヒープ ソート 0.5005 秒
バブル改ソート 0.5490 秒
バブル ソート 1401.4100 秒
となり、バブルソートが劇的に改善されたことが分かります。この時間は動作させる環境によって変わりますので、あくまでも比として考えて下さい。
このように、それまで処理速度が遅かったプログラムがちょっとした変更で性能が向上する可能性があるかも知れませんので、色々と考えてみるのも無駄でないと思います。
それではまた次回。
