並べ換え

二分法は効果的な検索方法だが、元のデータが小さい順に並んでいないと 適用することができない。他にも、元のデータを並べ換えておいたほうが 以後の処理がスムーズに進むことが多い。

ここでは配列に乱雑に入っているデータを小さい順に並べ換える方法に ついて説明することとする。

並べ換えの基本要素

もっとも簡単な並べ換えは要素数二つのものである。トランプのカードも 二枚だけなら、「そのまま」、または「二つを入れ換える」ことで小さい順に並 べることができる。この「二つを入れ換える」ことが並べ換えの基本操作であり、 どんなにカードが多いときもこの操作を繰り返すことで最後にはすべての並べ換 えが完了する。実際に二つの数を入れ換える操作を考えてみよう。いま、 x[]という整数配列に2個の数値が入っているとする。

x[0]x[1]
205

これを小さい順にするためには、x[0]とx[1]の値を 入れ換える必要がある。二つのコップに入った二種類のジュースを入れ換えるた めにはいったんもう一つのコップに移さなければできないのと同様 二つの変数を入れ換えるためには一時退避用の変数が必要で、次のようにする。 

 int tmp;         /* 退避用変数 */
   :
 tmp = x[0];      /* 退避用変数に一時保存 */
 x[0] = x[1];     /* x[0]にx[1]をコピー(上書きになる) */
 x[1] = tmp;      /* x[1]に昔のx[0]に入っていた値をコピー */

単純ソート

続いて、もっとも単純だがもっとも効率の悪い並べ換えの方法、 通称「馬鹿ソート」と呼ばれる方法について説明する。 この方法は、たくさんある配列中の値のうち、一番左にあるものに着目し、 それより右にあるものすべてと順次比較して行く。もし、左端にある値より 小さいものがあればそれと左端を交換し、継続してどんどん右へと比べていく。 右端まで全部調べたら、今度は左から二番目に着目して同様の操作を繰り返す。 さらに着目点を左から三番目、四番目、と進めて行って、右から二番目まで 操作を繰り返すと並べ換えが完了する。 プログラム風に表現すると次のようになる。 以下の例で変数 N はデータの個数を保持しているものとする。

 for (left=0; left<N-1; left++) { /* 着目点は0〜右端-1まで */
   for (i=left+1; i<N; i++) {
     /* 比較対象は着目点+1 〜 右端まで */
     if (data[left] > data[i]) { /* 着目点の値のほうが大きかったら */
       int tmp = data[left];        /* 入れ換える */
       data[left] = data[i];
       data[i] = tmp;
     }
   }
 }

クイックソート

比較的単純なアルゴリズムであるにもかかわらず最高速の部類に入ると いわれるクイックソートを紹介しておく。クイックソートを言葉で表現すると 次のようになる。

  1. 並べ換えるべき要素数が1なら何もせず終了

  2. まず真中へんに位置されている値に一つ着目する

  3. データを左から眺めていって着目した値と比較する

  4. 着目値より小さいものは着目値より左側に、
    着目値より大きいものは着目値より右側になるようにデータを移動する (着目値との左右関係さえあっていれば移動したデータどうしの順番はで たらめでよい)。

  5. データのならびが、
    「着目値より小さいグループ」、「着目値」、「着目値より大きいグルー プ」になっているので、小さいグループ、大きいグループ両方を クイックソートする。

  6. 終わり

クイックソートの手順の定義の途中に、再度クイックソート自身が出ている。 このような定義を再帰的定義という。 数学の証明問題で「数学的帰納法」を利用すると証明が簡潔に 書けるのと同様、再帰的定義用いることで、プログラムの構成を シンプルにすることができる。

実際のクイックソートのプログラムは非常に巧妙な書き方によって 実現されるていて少し難しくなっているので具体的なプログラムの説明は 省略するが、このように、ある問題を解くときに問題全体を 数個に分割し、分割した小さい集合を更に同様の手順で解くという 方法が有効であることを覚えておくとよい。

目次