第5回 プログラミングについて 『ソートの話』
『ソートの話』
ソートの話。ソートといえば、「いまさらソートの話なんて」と言われそうですが、ここではソートそのもののアルゴリズムをどうのこうのと解析する気はありません。これも、その手の専門書に詳しく書かれていますので詳細はそちらの方を参照して下さい。
さて、ソートとは何かを知らない人のために（知らない人はいないとは思いますが）ちょっとだけ。ソートとは「分類する」とか「そろえる」とかいった意味です。ここではその「そろえる」方の話しです。小さい値から、或は大きい値から並べることを一般にソートと言います。この並べ方の手法には様々な方法があります。その主だったものには、バブルソート、選択ソート、クイックソート、シェルソート、ヒープソートなどがあり、それぞれが特徴を持っています。
バブルソートは一般に遅いソートと言われますが、このソートが生き残っているのは安定したソートという特徴をもっているからです。安定というのは、１つのデータが複数の項目をもっているとき、その中の１つの項目についてだけを注目してソートをしても他の項目の順序が変化しないということを言います。
例えば、
Ａ:３、３、２、２、５、５、２、２、５
Ｂ:２、１、３、１、３、４、４、２、６
１つのデータがＡとＢの２つの項目を持っているとき、安定なソートのアルゴリズムを使ってＡについて小さい順から並べると、
Ａ:２、２、２、２、３、３、５、５、５
Ｂ:３、１、４、２、２、１、４、２、６
となり、同じＡの値（例えば２）についてはＢの順序が変化しません。これを安定と言います。
しかしながら一般的に安定したアルゴリズムのソートは遅いのが欠点です。それでは安定していないアルゴリズムで上記の様なソートができないのかと言えばそうではなくこれはあくまでも１つの項目について着目した場合なので、ＡとＢの両方に着目すればどのアルゴリズムでもこの結果は得られます。
かれこれ７、８年程昔の話しですが、実は私自身ソートのアルゴリズムは選択ソートとバブルソートぐらいしか知らなかった頃、バブルソートの変形版を自分で作って使用していたのですが、１万個程度のデータをソートする必要があってそのソートを使ったのですが、５～１０分程計算に時間がかかっていました。丁度そのころ同じ部署のＹ氏（この人はコンピュータの達人みたいな人でした）に、「別のソートでやったら自分の家のパソコンでは１５秒だったよ」と聞かされて愕然としたのを覚えています。それ以来ソートにはシェルソート（そのときＹ氏の使ったのがこのアルゴリズム）を信者の様に使っていますが、自分が作ったソートのアルゴリズムにも生き残る道があって、ソートされた配列の後尾に追加されたデータをソートすると、どのソートにも負けないので、配列に順次データを追加して結果を表示するなどというプログラムには使っています。
実際、私自身がプログラムを書くときには３種類程度のソートのアルゴリズムをデータの特性などを考慮して使っています。ランダムな値の大きな配列にはシェルソートを、整列している配列に追加するときにはバブルの変形を、１００個程度のデータをちょいとソートするときには選択ソートなどのように使い分けています。
さて、実際に純粋にデータをソートして結果を出力するのみといったプログラムは殆どありません。通常はソートはあくまでも結果を得るための手段の１つであることが多いのです。
例えば次の例。配列内で重複している値を表示するとしましょう。
Ａ：７、８、４、５、６、１、２、３、９、２、８
もしこの順序で並んでいるときに重複している値を捜し出すには、下に示すように最初の７に対しては残りの値全てについて検査が必要で、次の８についても同様なことが言えます。データの個数をＮとするとほぼＮ＊（Ｎー１）／２回の比較が必要で、Ｎの２乗に比例して回数が増加してしまいます。１０個程度ならば問題はありませんが、１００個、１０００個となると気の遠くなる回数の比較を行なわなければなりません。
Ａ：７、８、４、５、６、１、２、３、９、２、８
・・・ ・ ・ ・ ・ ・ ・ ・ ・ ・
・・・・・ ・ ・ ・ ・ ・ ・ ・ ・
・・・・・・・ ・ ・ ・ ・ ・ ・ ・
・・・・・・・・・ ・ ・ ・ ・ ・ ・
・・・・・・・・・・・ ・ ・ ・ ・ ・
・・・・・・・・・・・・・ ・ ・ ・ ・
・・・・・・・・・・・・・・・ ・ ・ ・
・・・・・・・・・・・・・・・・・ ・ ・
・・・・・・・・・・・・・・・・・・・ ・
・・・・・・・・・・・・・・・・・・・・・
これではよっぽど我慢強い人でないと耐えられないでしょう。そこでソートが登場するのです。ソートのアルゴリズムや時間には触れないとして、この配列Ａをソートすると、
Ａ：１、２、２、３、４、５、６、７、８、８、９
となります。これを見ると「なるほど」とすぐ納得してもらえると思います。隣どうしを比較すればよいことになります。
Ａ：１、 ２、 ２、 ３、 ４、 ５、 ６、 ７、 ８、 ８、 ９
・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・
こうするとＮー１回の比較回数になってしまいます。２つの配列の過不足を抽出するときも同じでソートされた２つの配列が次のようになったとき、
Ａ：１、２、３、４、７、８、９
Ｂ：１、２、４、６、７、８、９
Ａの１に対してはＢの１と２のみを、Ａの２に対してはＢの２と４のみを比較していけば良いことになります。
また配列の中から任意の値があるか否かを調べるときにもソートされていれば効率良く実行することができます。次の様にソートされた配列があったとします。
Ａ：１、２、４、６、７、８、９
いま１という値があるか否かをしらべるとき、単純に行なえば最初の要素から順番に比較ゆくと運良く最初に発見することができました。次に５を調べると最後まで比較しないと５がないことが分りません。１万個の要素数があったとすると１万回の比較が必要になる可能性があるということになります。
検索する方法を少し工夫し、最初に要素数の半分の位置と検索したい値との比較を行ないます。いま５を探そうとすると、配列Ａの要素数が７個ですからその中央の位置（７を整数の２で割ると３番目になる）の値４と比較すると、５はそれよりも大きい方向にあることが分ります。すなわち４番目から７番目のどこかにある可能性があるので、４番目と７番目の中央の位置である５番目（（４＋７）／２＝５）の値７と比較します。７は５より大きいですから５は３番目より後で５番目よりも前にある可能性があるので、最後は４番目の値６と比較すれば結果が得られます。
この例では配列の要素数が７個でしたので効果があまり分りませんが、一回の比較で領域を半分づつ減らして行きますので、１００００個の要素数のときには、５０００→２５００→１２５０→６２５→３１２→１５６→７８→３９→１８→９→４→２→１と確実に減りますので、１３回の比較で結果を得ることができるということになります。
簡単ですが次の関数がその例です、
search(int val,int *array,int narray)
{
int il,ic,ih;
il=0;
ih=narray-1;
while(il<=ih){
ic=(il+ih)/2;
if(val< array[ic])ih=ic-1;
else if(val==array[ic])return 1;
else il=ic+1;
}
return 0;
}
ソートされた要素数 narray の配列 array に val があれば 1 を、なければ 0 を返します。
リスト構造になっているデータをソートする場合はちょっと厄介な話しになります。
（リスト構造とは１つのデータが次のデータをポインタで指し示すような構造です）
このときには単純には高速なソートを行なえません。データを１つ１つたどって比較していけば可能ですが、これでは総当たりになってしまいます。一般にソートのアルゴリ
ズムは配列構造のもの（次のデータがすぐ隣に並んでいる構造）に対してですので、これには少し工夫して強引に配列のソートを行なうようにします。
余分にメモリーを使いますがリスト構造を示す配列を用意し、それにリストデータのアドレスを入れ、ポインタの配列をソートした後、リストの順序を変更するという手順で行ないます。
次のリストはちょっと長い例になってしまいますが、何かの参考にして下さい。
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
struct list_strct{ /* リストの構造の定義 */
int val;
struct list_strct *next;
};
main()
{
#define MAX_DATA 100
struct list_strct *list;
struct list_strct *prev,*cur;
int i;
/* MAX_LIST 個のリストを作る */
prev=NULL;
for(i=0;i<MAX_DATA;i++){
cur =malloc(sizeof(struct list_strct));
cur->val=rand(); /* 値はランダム関数から得る */
cur->next=NULL;
if(prev==NULL)list=cur;
else prev->next=cur;
prev=cur;
}
sort(&list); /* ソートを行なう */
cur=list; /* 結果の表示 */
while(cur){
printf("%d\n",cur->val);
cur=cur->next;
}
free(list);
#undef MAX_DATA
}
/* リスト構造のデータをソートする関数１ */
sort(struct list_strct **list)
{
struct list_strct *cur,*tmp;
struct list_strct **array;
int total;
int i,j;
/* リストのデータ数を得る */
for(cur= *list,total=0;cur;cur=cur->next,total++);
/* リストを指し示す配列を作る */
array=malloc(sizeof(struct list_strct *)*total);
/* 配列にリストのアドレスを代入する */
for(i=0,cur= *list;i<total;i++,cur=cur->next)array[i]=cur;
/* 配列をソートする（選択ソート）*/
for(i=0;i<total;i++){
for(j=i+1;j<total;j++){
if(array[i]->val>array[j]->val){
tmp =array[i];
array[i]=array[j];
array[j]=tmp ;
}
}
}
/* リストをつなぎ変える */
cur=NULL;
for(i=0;i<total;i++){
if(cur==NULL)*list=array[i];
else cur->next=array[i];
array[i]->next=NULL;
cur=array[i];
}
/* 使用したメモリーの解放 */
free(array);
}
この例ではリストを指し示す配列内のアドレス値をソートしています。この例の様にリ
ストの構造が単純で小さいときには、次の様に直接リストの値を変えてしまった方が効
率が良いでしょう。
/* リスト構造のデータをソートする関数２ */
sort(struct list_strct **list)
{
struct list_strct *cur;
struct list_strct **array;
int total,tmp;
int i,j;
/* リストのデータ数を得る */
for(cur= *list,total=0;cur;cur=cur->next,total++);
/* リストを指し示す配列を作る */
array=malloc(sizeof(struct list_strct *)*total);
/* 配列にリストのアドレスを代入する */
for(i=0,cur= *list;i<total;i++,cur=cur->next)array[i]=cur;
/* 配列をソートする（選択ソート）*/
for(i=0;i<total;i++){
for(j=i+1;j<total;j++){
if(array[i]->val>array[j]->val){
tmp =array[i]->val;
array[i]->val=array[j]->val;
array[j]->val=tmp ;
}
}
}
/* 使用したメモリーの解放 */
free(array);
}
ソートの関数１の方式をとるか２の方式をとるかは、ソートするリストの構造によって判断します。要するにどちらの方がソート時のメモリーの移動が少ないかによって値そのものを変えるか、ポインタのみを変更するかを決定します。
文字列のソートを行なうとき、次のように文字を整数値として整列したいときがあります。
１００
２０
１１００
５０
４
１２
単純に文字列のソートを行なうと、
１００
１１００
１２
２０
４
５０
という結果になってしまいます。これは文字列を先頭から１バイトづつ比較して大きいか小さいかを調べているためにこの結果となってしまうのです。もし、数値として見たときに整列させるには、単純には文字列を整数値に直して整数値どうしの比較を行なえばいいのですが、次の様に全ての文字列の最大長になるように右詰めを行なった文字列にして比較を行なっても同じ結果となります。
内部的に文字列を右詰めします。
１００
２０
１１００
５０
４
１２
この文字列を単純にソートすると、
４
１２
２０
５０
１００
１１００
となるので右詰めしていない文字列を出力すると、
４
１２
２０
５０
１００
１１００
となります。
今回はありふれた技法のソートの使い方の例をお話ししましたが、何かの参考にでもして下さい。それではまた次回。
