第51回 プログラミングについて『ソートを考える その１』
以前にソートの使い方をお話したことがありましたが、今回はソートそのものを考えてみましょう。ソートのアルゴリズムについては昔から多くの方が驚異的なものを発明しており、現在では新しいアルゴリズムは出尽くした感があります。しかしながらソートのアルゴリズムを研究してみることで、別の問題を解決するときに役に立つことがあるかと思います。
∴例は整数の配列を小さい順に並べるソートとし、要素巣がＮのとき配列の要素が０番から始まりＮ－１番までとします。またソート関数の引数の要素数はＮー１を渡すものとします。
プログラムを勉強して最初に覚えるソートといえばバブルソートです。バブルといえばバブル経済の崩壊を連想させ、リストラなどの暗いことを思い出すのですが、このソートアルゴリズムは別に陰惨なものではありません。このソートはアルゴリズムが簡単で、コーディングするのも楽なのでちょっとしたソートには結構使用されています。
このアルゴリズムは、配列の先頭の要素から順番に隣の要素と比較して隣のものが小さいときに要素を交換します。配列の最後までこれを行なったとき、もし要素の交換を行なっていたら再び配列の先頭からこれを繰返し、交換がなくなるまで行ないます。
２５３１４
↑↑
２５３１４
↑↑ 交換
２３５１４
↑↑ 交換
２３１５４
↑↑ 交換
２３１４５
交換があったので再び繰返す
２３１４５
↑↑
２３１４５
↑↑ 交換
２１３４５
↑↑
２１３４５
↑↑
２１３４５
交換があったので再び繰返す
２１３４５
↑↑ 交換
１２３４５
↑↑
１２３４５
↑↑
１２３４５
↑↑
１２３４５
交換があったので再び繰返す
１２３４５
↑↑
１２３４５
↑↑
１２３４５
↑↑
１２３４５
↑↑
１２３４５
交換がなかったので終わり
といった動作になります。このように交換がポチポチッと泡が立つように見えるところからバブルソートという名前がついたそうです。このソートは隣同士の要素と比較するので、安定なソートになります。安定なソートというのは１つの要素に複数の項目があったときに、他の項目の順番が乱れないことです。次の図のように１つの要素が数値とアルファベットを持っていたときに数値に着目してソートを行なったとします。
ａｂｃｄｅ
２１１２１
↑↑
ｂａｃｄｅ
１２１２１
↑↑
ｂｃａｄｅ
１１２２１
↑↑
ｂｃａｄｅ
１１２２１
↑↑
ｂｃａｅｄ
１１２１２
↑↑
ｂｃａｅｄ
１１２１２
↑↑
ｂｃａｅｄ
１１２１２
↑↑
ｂｃｅａｄ
１１１２２
このような結果になり、数値が１の要素のアルファベットも２の要素のアルファベットもそれぞれの順番が元のままなのです。
このアルゴリズムをプログラムにすると、
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);
}
このソートは配列のすべての要素が小さい順で並んでいるときには非常に高速に動作します。というのも一回配列全体を比較して交換がなければそれで終了となるからです。しかしながら次のように配列の最後に小さい値がある場合は遅くなってしまいます。
２３４５６７８９１
これがこのソートの泣き所といえるかも知れません。
バブルソートの変形もいくつかありますが、現在でも時々私が使用しているものを紹介しましょう。このソートは１０年程前に自分で作ったものです（多分誰かがすでに作っているものと思いますが）。
csort(data,ldata)
int *data;
int ldata;
{
int i,j,t;
for(i=0;i<ldata;i++){
j=i;
while(j>=0 && data[j]>data[j+1]){
t =data[j+1];
data[j+1]=data[j ];
data[j ]=t;
j--;
}
}
}
このソートは、バブルソートと同じように配列の最初の要素から順に隣の要素と比較し、交換を行なったら１つ前の要素と比較を行ない交換がなくなるまで行ないます。交換がなくなったら、交換を最初に行なった要素の次の要素から再び比較を行ない、最後の要素に到達したら終了です。次の図のような動作になります。
２５３１４
↑↑
２５３１４
↑↑
２３５１４
↑↑
２３５１４
↑↑
２３１５４
↑↑
２１３５４
↑↑
１２３５４
↑↑
１２３４５
↑↑
１２３４５
このソートは基本的にはバブルソートなのですが、バブルソートのような無駄な比較は格段に少なくなります。更に最後の要素が最も小さい値のときには、
２３４５６７８９１
↑↑
２３４５６７８９１
↑↑
２３４５６７８９１
↑↑
２３４５６７８９１
↑↑
２３４５６７８９１
↑↑
２３４５６７８９１
↑↑
２３４５６７８９１
↑↑
２３４５６７８９１
↑↑
２３４５６７８１９
↑↑
２３４５６７１８９
↑↑
２３４５６１７８９
↑↑
２３４５１６７８９
↑↑
２３４１５６７８９
↑↑
２３１４５６７８９
↑↑
２１３４５６７８９
↑↑
２１３４５６７８９
↑↑
１２３４５６７８９
となり、非常に高速に動作します。配列の値がランダムでもバブルソートよりも高速ですが、上の場合のように最後の要素のみが小さいときには最高の速度になるので、配列に要素を追加するたびにソートを行なうときには最も適しており、クイックソートやシェルソートなどよりもはるかに高速に動作します。ちなみにこのソートを自分では交換がなくなるまで追いかけていくので、キャッチアップソート（追いかけっこソート）と自分では呼んでいます。実はこのソートは挿入ソートと基本的には同じです。
次に考える選択ソートはバブルソートと違って、どんな場合でも遅いアルゴリズムです。このソートは配列の最初の要素から順に、それ以降のすべての要素と比較し、その要素の方が小さいときに交換を行なうものです。図でその動作を見てみましょう。
２５３１４
↑↑
２５３１４
↑ ↑
２５３１４
↑ ↑ 交換
１５３２４
↑ ↑
１５３２４
↑↑ 交換
１３５２４
↑ ↑ 交換
１２５３４
↑ ↑
１２５３４
↑↑ 交換
１２３５４
↑ ↑
１２３５４
↑↑ 交換
１２３４５
ssort(data,ldata)
int *data;
int ldata;
{
int i,j,t;
for(i=0;i<ldata;i++){
for(j=i+1;j<=ldata;j++){
if(data[i]>data[j]){
t =data[i];
data[i]=data[j];
data[j]=t;
}
}
}
このアルゴリズムは配列が小さい順で並んでいてもとにかく総当たりでソートしますので、どんな場合でもソートに時間が掛かる上、安定ではありません。このソートも変形があり、交換が必要なときにその場で交換するのではなく、最後に交換をするようにするものもあります。
ssort(data,ldata)
int *data;
int ldata;
{
int i,j,k,t;
for(i=0;i<ldata;i++){
k=i;
for(j=i+1;j<=ldata;j++){
if(data[k]>data[j])k=j;
}
if(k!=i){
t =data[i];
data[i]=data[k];
data[k]=t;
}
}
}
このようにしても交換回数が減るぶんだけ速くなりますが比較回数は変りません。
次は有名な高速ソートを紹介しますが、長くなりますので次回にします。
