第52回 プログラミングについて『ソートを考える その２』
今回は有名な高速ソートについて考えてみます。
まずヒープソートというアルゴリズムを見てみましょう。実際の動作を考える前にヒープ木を理解した方がいいと思います。ヒープ木とは
１
┌─┴─┐
２ ３
┌┴┐ ┌┴┐
４ ５ ６ ７
┌┴┐
８ ９
といった感じの木です。つまり木の根が一番小さい値で、その葉には次に小さい値が伸びるような構造になります。問題はこの木の構造をどのように配列内で実現するかということなのですが、１つの根と葉の構造を考えてみると要素の数は３つになります。配列の要素番号が１から始まるとすると、この木の根の要素番号がＮ番目のときに、葉をそれぞれＮ＊２とＮ＊２＋１となる場所に葉があるとします。
まずこの関係を根が最大になるように葉を並べ替えます。このとき木の末端の１つの木から計算を行ないます。この例の場合は最大数は９ですので９／２＝４が末端の親になります。また葉どうしの大小はどちらでも構いません。
３８２７６１５４９ 親の値７を記憶しておく。
↑ ↑↑
親 子子
３８２９６１５４９ ２つ子のうち大きい方を親に入れ、その子を親とする。
↑ このときこれ以上子がないので、記憶しておいた値を
親 親に代入する。
３８２９６１５４７ 次に１つ前の木について同じことを行なう。
↑ ↑↑ 親の値２を記憶しておく。
親 子子
３８５９６１５４７ ２つ子のうち大きい方を親に入れ、その子を親とする。
↑ このときこれ以上子がないので、記憶しておいた値を
親 親に代入する。
３８５９６１２４７ 次に１つ前の木について同じことを行なう。
↑ ↑↑ 親の値８を記憶しておく。
親 子子
３９５９６１２４７ このときどちらの子も記憶してある値８より小さいので、
↑ ↑↑ 親に記憶してある値８を代入し、これ以上の子の計算は
親 子子 行なわない。
３９５８６１２４７ 次に１つ前の木について同じことを行なう。
↑↑↑ 親の値３を記憶しておく。
親子子
９９５８６１２４７ ２つ子のうち大きい方を親に入れ、その子を親とする。
↑ ↑↑
親 子子
９８５８６１２４７ ２つ子のうち大きい方を親に入れ、その子を親とする。
↑ ↑↑
親 子子
９８５７６１２４７ ２つ子のうち大きい方を親に入れ、その子を親とする。
↑ このときこれ以上子がないので、親に記憶しておいた値３
親 を代入する。
９８５７６１２４３
これで降順のヒープ木ができあがります。この結果を分かりやすく見てみると、
９
┌─┴─┐
８ ５
┌┴┐ ┌┴┐
７ ６ １ ２
┌┴┐
４ ３
もう少し分かりやすくすると、
９
┌─┴─┐
５ ８
┌┴┐ ┌┴┐
１ ２ ６ ７
┌┴┐
４ ３
となり、木の根からみればどの葉も親よりも小さくなります。
このようにしてできたヒープ木の根が最大値になっているので、この値と配列の最後の値を交換し配列の数を１つ減らします。
３
┌─┴─┐
８ ５
┌┴┐ ┌┴┐
７ ６ １ ２
┌┴┐
４ ９
というヒープ木にし、要素が１つ減った配列とします。
３
┌─┴─┐
８ ５
┌┴┐ ┌┴┐
７ ６ １ ２
│
４
このとき、ヒープ木の根以外の関係は既に完成していますので、今度はヒープ木の根から子の関係を計算し直します。やり方は上の方法と同じです。
３８５７６１２４ ９
↑↑↑
親子子
８８５７６１２４ ９
↑ ↑↑
親 子子
８７５７６１２４ ９
↑ ↑↑
親 子子
８７５４６１２４ ９
↑
親
８７５４６１２３ ９
これで再びヒープ木ができましたので、配列の先頭と最後を交換し、同じ事を繰返します。以下特に説明はしませんが経過のみを書きます。
３７５４６１２ ８９
↑↑↑
親子子
７７５４６１２ ８９
↑ ↑↑
親 子子
７６５４６１２ ８９
↑
親
７６５４３１２ ８９
２６５４３１ ７８９
↑↑↑
親子子
６６５４３１ ７８９
↑ ↑↑
親 子子
６４５４３１ ７８９
↑
親
６４５２３１ ７８９
１４５２３ ６７８９
↑↑↑
親子子
５４５２３ ６７８９
↑
親
５４１２３ ６７８９
３４１２ ５６７８９
↑↑↑
親子子
４４１２ ５６７８９
↑ ↑
親 子
４３１２ ５６７８９
２３１ ４５６７８９
↑↑↑
親子子
３３１ ４５６７８９
↑
親
３２１ ４５６７８９
１２ ３４５６７８９
↑↑
親子
２２ ３４５６７８９
↑
親
２１ ３４５６７８９
１ ２３４５６７８９
１２３４５６７８９
というようになります。
この一連の動作を見てみると、非常に巧妙なアルゴリズムであることが理解できると思います。配列の中にヒープ木の構造を仮想的に作成する方法（Ｎが親なら、Ｎ＊２とＮ＊２＋１が子の関係）、最初にヒープ木を作成するときに末端の木から行なうなどなかなか思い付かないものです。さてこれをプログラムにしてみましょう。
sort(int *data,int ldata)
{
int i,j,k,t;
data--;
ldata++;
for(k=ldata/2;k>=1;k--){
i=k;
t=data[k];
while((j=i*2)<=ldata){
if(j<ldata && data[j]<data[j+1])j++;
if(t>=data[j])break;
data[i]=data[j];
i=j;
}
data[i]=t;
}
while(ldata>1){
t =data[ldata];
data[ldata]=data[1 ];
ldata--;
i=1;
while((j=i*2)<=ldata){
if(j<ldata && data[j]<data[j+1])j++;
if(t>=data[j])break;
data[i]=data[j];
i=j;
}
data[i]=t;
}
}
今回の関数の約束事が配列の要素数の引数は要素数ー１ですので、関数の最初に配列のアドレスを１要素分だけ負に移動し、要素数を１つ増やしています。こうすると関数内では配列の添字が１からとすることができ、このアルゴリズムをスッキリ表現することができます。
次にシェルソートというアルゴリズムを見てみましょう。このアルゴリズムはソートの初期におおざっぱにソートをし、だんだんと正確にソートを行なっていこうとするものです。言い換えると、最初は大きくジャンプした方がいい要素をだいたいの位置に置き、だんだんとあるべき位置に収束させようというものです。
次の例の要素数が９ですので、比較する要素の間隔をその半分の４とします。
３８２７６１５４９
↑ ↑
３８２７６１５４９
↑ ↑ 交換
３１２７６８５４９
↑ ↑
３１２７６８５４９
↑ ↑ 交換
３１２４６８５７９
↑ ↑
３１２４６８５７９
次に比較間隔を半分の２にします。
３１２４６８５７９
↑ ↑ 交換
２１３４６８５７９
↑ ↑
２１３４６８５７９
↑ ↑
２１３４６８５７９
↑ ↑
２１３４６８５７９
↑ ↑ 交換。
交換したときには交換がなくなるまで前の要素と比較する。
２１３４５８６７９
↑ ↑ 前の要素との比較。
２１３４６８５７９
↑ ↑
２１３４６７５８９
↑ ↑
２１３４６８５７９
↑ ↑
２１３４６８５７９
次に比較間隔を半分の１にし、同様に行ないます。
２１３４６８５７９
↑↑
１２３４６８５７９
↑↑
１２３４６８５７９
↑↑
１２３４６８５７９
↑↑
１２３４６８５７９
↑↑
１２３４６８５７９
↑↑
１２３４６５８７９
↑↑
１２３４５６８７９
↑↑
１２３４５６８７９
↑↑
１２３４５６７８９
↑↑
１２３４５６７８９
↑↑
１２３４５６７８９
これでソートが終了です。非常に単純なアルゴリズムですがこれも嬉しいくらいに高速です。この例では比較の間隔縮小率を０．５としましたが、この間隔縮小率の違いでソート時間が変ります。
これをプログラムにしてみましょう。
ssort(data,ldata)
int data[];
int ldata;
{
int i,j,t,gap;
gap=(ldata+1)/2;
while(gap){
i=gap;
while(i<=ldata){
j=i-gap;
while(j>=0 && data[j]>data[j+gap]){
t =data[j ];
data[j ]=data[j+gap];
data[j+gap]=t ;
j-=gap;
}
i++;
}
gap/=2;
}
}
以外に簡単なプログラムになってしまいました。
最後に最も有名はクイックソートを考えてみましょう。このアルゴリズムは、ある値よりも小さいグループと大きいグループに分け、順次それぞれのグループを小さいものと大きいものとに分けてそれ以上に分けることができなくなったときにソートが完成するというものです。通常ある値は配列の中央の要素の値を使用します。
まず動作を見てみましょう。配列の要素の数が９ですのでその半分の位置は（９ー１
）／２＝４となり値は７です。
３８２７６１５４９ ４番目の要素と最初の要素を交換します。
↑ ↑
７８２３６１５４９ ８は７より大きいのでそのまま。
↑↑
７８２３６１５４９ ２は７以下なので、７の次の要素と交換します。
↑ ↑
７２８３６１５４９ ３は７以下なので、２の次の要素と交換します。
↑ ↑
７２３８６１５４９ ６は７以下なので、３の次の要素と交換します。
↑ ↑
７２３６８１５４９ １は７以下なので、６の次の要素と交換します。
↑ ↑
７２３６１８５４９ ５は７以下なので、１の次の要素と交換します。
↑ ↑
７２３６１５８４９ ４は７以下なので、５の次の要素と交換します。
↑ ↑
７２３６１５４８９ ９は７より大きいのでそのまま。
↑ ↑
７２３６１５４８９ 最後に先頭と４を交換。
↑ ↑
４２３６１５ ７ ８９
これで２つのグループができました。次に７以下のグループを２つに分けます。このグループの要素数は６ですので中央の位置は（６ー１）／２＝２で値は３です。以下同様ですので説明は省略します。
４２３６１５ ７ ８９
↑ ↑
３２４６１５ ７ ８９
↑↑
３２４６１５ ７ ８９
↑↑
３２４６１５ ７ ８９
↑ ↑
３２４６１５ ７ ８９
↑ ↑
３２１６４５ ７ ８９
↑ ↑
３２１６４５ ７ ８９
↑ ↑
１２３６４５ ７ ８９
１２ ３ ６４５ ７ ８９
↑↑
１２ ３ ４６５ ７ ８９
↑↑
１２ ３ ４６５ ７ ８９
↑ ↑
１２ ３ ４６５ ７ ８９
１２ ３ ４ ６５ ７ ８９
↑
１２ ３ ４ ６５ ７ ８９
↑↑
１２ ３ ４ ６５ ７ ８９
↑
１２ ３ ４ ６５ ７ ８９
↑↑
１２ ３ ４ ５ ６ ７ ８９
となります。部分配列を再び同様にソートするのでプログラムを作成するには工夫が必要になります。Ｂ．Ｗ．カーニハンとＤ．Ｍ．リッチーの書いた『プログラミング言語Ｃ』にクイックソートがでており、かなりスッキリとまとめてあるので紹介します（今回の例の関数の形式に合わせて少し書き直しています）。
qsort(data,ldata)
int *data;
int ldata;
{
qsort_task(data,0,ldata);
}
qsort_task(data,left,right)
int *data;
int left,right;
{
int i,last,t;
if(left<right){
t =data[ left ];
data[ left ]=data[(left+right)/2];
data[(left+right)/2]=t;
last=left;
for(i=left+1;i<=right;i++){
if(data[left]>data[i]){
last++;
t =data[last];
data[last]=data[i ];
data[i ]=t;
}
}
t =data[last];
data[last]=data[left];
data[left]=t;
qsort_task(data,left ,last-1);
qsort_task(data,last+1,right );
}
}
実は上の動作の説明はこの関数を基にしているのですが、再帰呼び出しを使用してスマートにまとめているのには感心させられます。もし再帰呼び出しを行なわずにクイックソートを行なおうとすれば別に配列を用意する必要があるので結構面倒になります。厳密に考えれば再帰呼び出しを行なうということでそれに相当する（以上）のメモリーを消費しています。またスタックに余裕がないときには配列の要素数が大きくなると動作しないこともありますが、何にしてもＵＮＩＸ上での動作を基本にした書籍ですのでこのように記述している訳です。
どのソートが最も高速なのかはここでは論議はしませんが、私の好みではシェルソートです。アルゴリズムもプログラムも単純で余分なメモリーも消費しないのが大きな理由です。
ところで、前回説明したソートと今回説明したソートと比較すると、特殊な条件を除けば今回のものの方が遥かに高速に動作するのですが、一体どうしてこの差が出てしまうのでしょうか。ここがソートのアルゴリズムを考えるときの大きな注目点になります。
前回のソートは、配列の最初の要素から順に決定していくのに対し、今回のものは全体が徐々に決定されていくところにあります。言い換えれば、ソートの初期には大きく移動すべきものはだいたいの場所に一気に移動させ、徐々に本来の位置に収束させていくやり方をとっているのです。芋虫が這い回るように隣同士と交換していくよりは、バッタが飛び跳ねるように目標のそばに跳んでいく方が効率が良くなる訳です。
それではまた次回。
