プリント基板設計・シミュレーション

TOP > アポロレポート > コラム > 第5回 プログラミングについて
コラム
2022/05/06

第5回 プログラミングについて

アポロレポート

『ソートの話』


ソートの話。ソートといえば、「いまさらソートの話なんて」と言われそうですが、ここではソートそのもののアルゴリズムをどうのこうのと解析する気はありません。これも、その手の専門書に詳しく書かれていますので詳細はそちらの方を参照して下さい。
さて、ソートとは何かを知らない人のために(知らない人はいないとは思いますが)ちょっとだけ。ソートとは「分類する」とか「そろえる」とかいった意味です。ここではその「そろえる」方の話しです。小さい値から、或は大きい値から並べることを一般にソートと言います。この並べ方の手法には様々な方法があります。その主だったものには、バブルソート、選択ソート、クイックソート、シェルソート、ヒープソートなどがあり、それぞれが特徴を持っています。
バブルソートは一般に遅いソートと言われますが、このソートが生き残っているのは安定したソートという特徴をもっているからです。安定というのは、1つのデータが複数の項目をもっているとき、その中の1つの項目についてだけを注目してソートをしても他の項目の順序が変化しないということを言います。
例えば、

  A:3、3、2、2、5、5、2、2、5
  B:2、1、3、1、3、4、4、2、6

1つのデータがAとBの2つの項目を持っているとき、安定なソートのアルゴリズムを使ってAについて小さい順から並べると、

  A:2、2、2、2、3、3、5、5、5
  B:3、1、4、2、2、1、4、2、6

となり、同じAの値(例えば2)についてはBの順序が変化しません。これを安定と言います。
しかしながら一般的に安定したアルゴリズムのソートは遅いのが欠点です。それでは安定していないアルゴリズムで上記の様なソートができないのかと言えばそうではなくこれはあくまでも1つの項目について着目した場合なので、AとBの両方に着目すればどのアルゴリズムでもこの結果は得られます。

かれこれ7、8年程昔の話しですが、実は私自身ソートのアルゴリズムは選択ソートとバブルソートぐらいしか知らなかった頃、バブルソートの変形版を自分で作って使用していたのですが、1万個程度のデータをソートする必要があってそのソートを使ったのですが、5~10分程計算に時間がかかっていました。丁度そのころ同じ部署のY氏(この人はコンピュータの達人みたいな人でした)に、「別のソートでやったら自分の家のパソコンでは15秒だったよ」と聞かされて愕然としたのを覚えています。それ以来ソートにはシェルソート(そのときY氏の使ったのがこのアルゴリズム)を信者の様に使っていますが、自分が作ったソートのアルゴリズムにも生き残る道があって、ソートされた配列の後尾に追加されたデータをソートすると、どのソートにも負けないので、配列に順次データを追加して結果を表示するなどというプログラムには使っています。
実際、私自身がプログラムを書くときには3種類程度のソートのアルゴリズムをデータの特性などを考慮して使っています。ランダムな値の大きな配列にはシェルソートを、整列している配列に追加するときにはバブルの変形を、100個程度のデータをちょいとソートするときには選択ソートなどのように使い分けています。

さて、実際に純粋にデータをソートして結果を出力するのみといったプログラムは殆どありません。通常はソートはあくまでも結果を得るための手段の1つであることが多いのです。
例えば次の例。配列内で重複している値を表示するとしましょう。

  A:7、8、4、5、6、1、2、3、9、2、8

もしこの順序で並んでいるときに重複している値を捜し出すには、下に示すように最初の7に対しては残りの値全てについて検査が必要で、次の8についても同様なことが言えます。データの個数をNとするとほぼN*(Nー1)/2回の比較が必要で、Nの2乗に比例して回数が増加してしまいます。10個程度ならば問題はありませんが、100個、1000個となると気の遠くなる回数の比較を行なわなければなりません。

  A:7、8、4、5、6、1、2、3、9、2、8
       ・・・ ・ ・ ・ ・ ・ ・ ・ ・ ・
       ・・・・・ ・ ・ ・ ・ ・ ・ ・ ・
       ・・・・・・・ ・ ・ ・ ・ ・ ・ ・
       ・・・・・・・・・ ・ ・ ・ ・ ・ ・
       ・・・・・・・・・・・ ・ ・ ・ ・ ・
       ・・・・・・・・・・・・・ ・ ・ ・ ・
       ・・・・・・・・・・・・・・・ ・ ・ ・
       ・・・・・・・・・・・・・・・・・ ・ ・
       ・・・・・・・・・・・・・・・・・・・ ・
       ・・・・・・・・・・・・・・・・・・・・・

これではよっぽど我慢強い人でないと耐えられないでしょう。そこでソートが登場するのです。ソートのアルゴリズムや時間には触れないとして、この配列Aをソートすると、

  A:1、2、2、3、4、5、6、7、8、8、9

となります。これを見ると「なるほど」とすぐ納得してもらえると思います。隣どうしを比較すればよいことになります。

  A:1、 2、 2、 3、 4、 5、 6、 7、 8、 8、 9
       ・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・

こうするとNー1回の比較回数になってしまいます。2つの配列の過不足を抽出するときも同じでソートされた2つの配列が次のようになったとき、

  A:1、2、3、4、7、8、9
  B:1、2、4、6、7、8、9

Aの1に対してはBの1と2のみを、Aの2に対してはBの2と4のみを比較していけば良いことになります。

また配列の中から任意の値があるか否かを調べるときにもソートされていれば効率良く実行することができます。次の様にソートされた配列があったとします。

  A:1、2、4、6、7、8、9

いま1という値があるか否かをしらべるとき、単純に行なえば最初の要素から順番に比較ゆくと運良く最初に発見することができました。次に5を調べると最後まで比較しないと5がないことが分りません。1万個の要素数があったとすると1万回の比較が必要になる可能性があるということになります。
検索する方法を少し工夫し、最初に要素数の半分の位置と検索したい値との比較を行ないます。いま5を探そうとすると、配列Aの要素数が7個ですからその中央の位置(7を整数の2で割ると3番目になる)の値4と比較すると、5はそれよりも大きい方向にあることが分ります。すなわち4番目から7番目のどこかにある可能性があるので、4番目と7番目の中央の位置である5番目((4+7)/2=5)の値7と比較します。7は5より大きいですから5は3番目より後で5番目よりも前にある可能性があるので、最後は4番目の値6と比較すれば結果が得られます。

この例では配列の要素数が7個でしたので効果があまり分りませんが、一回の比較で領域を半分づつ減らして行きますので、10000個の要素数のときには、5000→2500→1250→625→312→156→78→39→18→9→4→2→1と確実に減りますので、13回の比較で結果を得ることができるということになります。
簡単ですが次の関数がその例です、

  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 を返します。

リスト構造になっているデータをソートする場合はちょっと厄介な話しになります。
(リスト構造とは1つのデータが次のデータをポインタで指し示すような構造です)
このときには単純には高速なソートを行なえません。データを1つ1つたどって比較していけば可能ですが、これでは総当たりになってしまいます。一般にソートのアルゴリ
ズムは配列構造のもの(次のデータがすぐ隣に並んでいる構造)に対してですので、これには少し工夫して強引に配列のソートを行なうようにします。
余分にメモリーを使いますがリスト構造を示す配列を用意し、それにリストデータのアドレスを入れ、ポインタの配列をソートした後、リストの順序を変更するという手順で行ないます。
次のリストはちょっと長い例になってしまいますが、何かの参考にして下さい。

  #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
  }
                                                               /* リスト構造のデータをソートする関数1 */
  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);
  }

この例ではリストを指し示す配列内のアドレス値をソートしています。この例の様にリ
ストの構造が単純で小さいときには、次の様に直接リストの値を変えてしまった方が効
率が良いでしょう。

                                                                /* リスト構造のデータをソートする関数2 */
  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);
  }

ソートの関数1の方式をとるか2の方式をとるかは、ソートするリストの構造によって判断します。要するにどちらの方がソート時のメモリーの移動が少ないかによって値そのものを変えるか、ポインタのみを変更するかを決定します。

文字列のソートを行なうとき、次のように文字を整数値として整列したいときがあります。

  100
  20
  1100
  50
  4
  12

単純に文字列のソートを行なうと、

  100
  1100
  12
  20
  4
  50

という結果になってしまいます。これは文字列を先頭から1バイトづつ比較して大きいか小さいかを調べているためにこの結果となってしまうのです。もし、数値として見たときに整列させるには、単純には文字列を整数値に直して整数値どうしの比較を行なえばいいのですが、次の様に全ての文字列の最大長になるように右詰めを行なった文字列にして比較を行なっても同じ結果となります。

内部的に文字列を右詰めします。

  100
  20
  1100
  50
  4
  12

この文字列を単純にソートすると、

  4
  12
  20
  50
  100
  1100

となるので右詰めしていない文字列を出力すると、

  4
  12
  20
  50
  100
  1100

となります。

今回はありふれた技法のソートの使い方の例をお話ししましたが、何かの参考にでもして下さい。それではまた次回。


そのお悩み、
アポロ技研に話してみませんか?

アポロ技研でワンランク上の物創りへ!
そのお悩み、アポロ技研に話してみませんか?