お気楽Ｃ++プログラミング超入門

はじめに

「整列 (sorting)」はある規則に従ってデータを順番に並べ換える操作です。たとえば、データが整数であれば大きい順に並べる、もしくは小さい順に並べます。一般に、このような操作を「ソート (sort)」と呼んでいます。

ソートは昔から研究されている分野で、優秀なアルゴリズムが確立しています。Yet Another C++ Problems (2) では、バブルソート、選択ソート、単純挿入ソートを取り上げました。要素数を \(N\) とすると、これらは \(N^2\) に比例する遅いソートです。今回はもっと速いソートを紹介しましょう。

●シェルソート

「シェルソート (shell sort)」は挿入ソートの改良版ともいえる方法です。最初は遠く離れた要素間でソートを開始し、徐々に間隔を狭めていきます。最後は隣り合った要素間でソートします。つまり、単純挿入ソートと同じになります。

間隔が大きいときは要素の個数が少ないので、単純なアルゴリズムでもソートにかかる時間は少なくてすみます。間隔が小さくなると要素の個数は多くなりますが、大まかにソートされているので挿入ソートでも高速にソートすることが可能です。

 9 5 3 7 6 4 2 8    最初の状態

 9       6          間隔を 4 で分割する
   5       4
     3       8
       7       2

 6       9          各群をソートする
   4       5
     3       8
       2       7

 6   3   9   8      間隔を 2 で分割する
   4   2   5   7

 3   6   8   9      各群をソートする
   2   4   5   7

 3 2 6 4 8 5 9 7    間隔を 1 で分割する（単純挿入ソートと同じ）

 2 3 4 5 6 7 8 9    ソート完了

      図 : シェルソート

プログラムは次のようになります。

リスト : シェルソート

void shell_sort(int buff[], int size)
{
  for (int gap = size / 2; gap > 0; gap /= 2) {
    for (int i = gap; i < size; i++) {
      int temp = buff[i];
      int j = i - gap;
      for (; j >=0 && temp < buff[j]; j -= gap)
        buff[j + gap] = buff[j];
      buff[j + gap] = temp;
    }
  }
}

最初のループで間隔を徐々に狭めていきます。ここでは単純に 2 で割っていくことにしました。次のループで比較する要素を取り出します。最後のループでこの要素を挿入する位置を探索します。このときの探索は隣り合った要素ではなく gap 離れた要素を比較します。

2 番目のループでは、各群を並列にソートしていることに注意してください。群のひとつの要素を取り出して位置を決めたら、次の群の要素を取り出して位置を決めています。最後に gap は 1 になるので、挿入ソートと同じになりソートが完了します。

シェルソートの場合、gap を常に奇数になるようにすると、実行速度はデータの個数 n の 1.5 乗に比例します。また、クヌース先生によると、gap の値に次の数列を用いると、シェルソートは n の 1.25 乗に比例するそうです。

gap = ..., 121, 40, 13, 4, 1

この数列は 3 倍して 1 を加えることで得られる数列を逆にしたものです。興味のある方は拙作のページ「お気楽Ｃ言語プログラミング超入門 : ソート」をお読みください。

●クイックソート

クイックソートはある値を基準にして、要素をそれより大きいものと小さいものの 2 つに分割していくことでソートを行います。2 つに分けた各々の区間を同様に分割して 2 つの区間に分けます。最後は区間の要素がひとつになってソートが完了します。

  9 5 3 7 6 4 2 8     最初の状態

  9 5 3 7 6 4 2 8     7 を枢軸にして左側から 7 以上の値を探し、
  L           R       右側から 7 以下の値を探す。

  2 5 3 7 6 4 9 8     交換する
  L           R

  2 5 3 7 6 4 9 8     検索する
        L   R

  2 5 3 4 6 7 9 8     交換する
        L   R

  2 5 3 4 6 7 9 8     検索する。R と L が交差したら分割終了。
          R L

  [2 5 3 4 6] [7 9 8] この 2 つの区間について再び同様な分割を行う

                図 : クイックソート

基準になる値のことを「枢軸 (pivot)」といいます。枢軸は要素の中から適当な値を選びます。今回は中央にある要素を選ぶことにしましょう。上図を見てください。左側から枢軸 7 以上の要素を探し、左側から 7 以下の要素を探します。探索のときは枢軸が番兵の役割を果たすので、ソート範囲外の要素を探索することはありません。見つけたらお互いの要素を交換します。探索位置が交差したら分割は終了です。

あとは同じ手順を分割した 2 つの区間に適用します。これは再帰定義を使えば簡単に実現できます。分割した区間の要素数が 1 になったときが再帰の停止条件になります。プログラムは次のようになります。

リスト : クイックソート

void qsort_sub(int buff[], int low, int high)
{
  int pivot = buff[low + (high - low) / 2];
  int i = low;
  int j = high;
  while (true) {
    while (pivot > buff[i]) i++;
    while (pivot < buff[j]) j--;
    if (i >= j) break;
    int temp = buff[i];
    buff[i] = buff[j];
    buff[j] = temp;
    i++;
    j--;
  }
  if (low < i - 1) qsort_sub(buff, low, i - 1);
  if (high > j + 1) qsort_sub(buff, j + 1, high);
}

void quick_sort(int buff[], int size)
{
  qsort_sub(buff, 0, size - 1);
}

実際の処理は関数 qsort_sub で行います。引数 buff がソートする配列、low が区間の下限値、high が区間の上限値です。qsort_sub は buff の low から high までの区間をソートします。最初に、区間の中央にあるデータを枢軸として選びます。そして、最初の while ループで pivot を基準にして区間を 2 つに分けます。

次の while ループで、左側から枢軸以上の要素を探しています。ここでは枢軸以上という条件を、枢軸より小さい間は探索位置を進める、というように置き換えています。同様に次の while ループで右側から枢軸以下の要素を探します。お互いの探索位置 i, j が交差したら分割は終了です。break 文で while ループから脱出します。そうでなければお互いの要素を交換します。交換したあとは i と j の値を更新しておくことを忘れないでください。

そして、分割した区間に対して quick_sort を再帰呼び出しします。このとき要素数をチェックして、2 個以上ある場合に再帰呼び出しを行います。この停止条件を忘れると正常に動作しません。ご注意ください。

●クイックソートの欠点

クイックソートは、枢軸の選び方で効率が大きく左右されます。区間の中央値を枢軸に選ぶと、区間をほぼ半分に分割することができます。この場合がいちばん効率が良く、データ数を \(N\) とすると \(N \log_2 N\) に比例する時間でソートすることができます。

逆に、区間での最大値または最小値を枢軸に選ぶと、区間はその要素と残りの要素の 2 つに分割にされることになります。これが最悪の場合で、分割のたびに最大値もしくは最小値を選ぶと、実行時間は要素数の 2 乗に比例することになります。これは遅いソートアルゴリズムであるバブルソートや単純挿入ソートと同じです。

この問題は枢軸の選び方を工夫することで、完全ではありませんが回避することができます。区間の中からいくつかの要素を選び、その中で中央の値を持つ要素を枢軸とします。たくさんの要素を選ぶとそれだけ最悪の枢軸を選ぶ危険性は少なくなりますが、値を選ぶのに時間がかかってしまいます。実際には数個の要素を選び、その中央値を枢軸とする場合が多いようです。興味のある方は拙作のページ「お気楽Ｃ言語プログラミング超入門 : ソート」をお読みください。

●マージソート

  9 5 3 7 6 4 2 8  最初の状態

 |5 9|3 7|4 6|2 8| 長さ２の列に併合

 |3 5 7 9|2 4 6 8| 長さ４の列に併合 

  2 3 4 5 6 7 8 9  ソート終了

        図 : マージソート

「マージ (併合 : merge)」とはソート済みの複数の列を一つの列にまとめる操作のことです。配列のマージは拙作のページ Yet Another C++ Problems (2) で取り上げました。このマージを使ったソートを「マージソート (merge sort)」といいます。上の図を見てください。

マージをソートに応用する場合、最初は各要素をソート済みの配列として考えます。この状態で隣の配列とマージを行い、長さ 2 の配列を作ります。次に、この配列に対して再度マージを行い、長さ 4 の配列を作ります。このように順番にマージしていくと、最後には一つの配列にマージされソートが完了します。

それではプログラムを作りましょう。配列の長さを 1, 2, 4, 8, ... と増やしていくよりも、再帰的に考えた方が簡単です。マージは 2 つの列を一つの列にまとめる操作です。そこで、まずソートする配列を 2 つに分けて、前半部分をソートします。次に後半部分をソートして、その結果をマージすればいいわけです。

では、どうやってソートするのかというと、再帰呼び出しするのです。そうすると、どんどん配列を 2 つに割っていくことになり、最後にデータが一つとなります。それはソート済みの配列と考えることができるので、再帰呼び出しを終了してマージ処理に移ることができます。あとはデータを順番にマージしていってソートが完了します。

プログラムは次のようになります。

リスト : マージソート

void msort_sub(int buff[], int low, int high, int work[])
{
  if (low >= high) return;
  int mid = low + (high - low) / 2;
  msort_sub(buff, low, mid, work);
  msort_sub(buff, mid + 1, high, work);
  // 前半部分を work に退避
  int i = low;
  for (; i <= mid; i++) work[i] = buff[i];
  int j = low, k = low;
  while (i <= high && j <= mid) {
    buff[k++] = work[j] <= buff[i] ? work[j++] : buff[i++];
  }
  while (j <= mid) buff[k++] = work[j++];
}

void merge_sort(int buff[], int n)
{
  int *work = new int[n];
  msort_sub(buff, 0, n - 1, work);
  delete[] work;
}

merge_sort は作業用のメモリ領域 work を取得して、関数 msort_sub を呼び出します。work の大きさは n / 2 で十分なのですが、今回は同じ大きさのメモリ領域を取得することにします。

msort_sub の引数 low, high がソートする区間を表します。最初の if 文で要素数をチェックします。low >= high であれば区間の要素数は 1 以下なのでソートを終了します。そうでなければ、区間の中央を求めて変数 mid にセットします。それから、区間を前半 (low, mid) と後半 (mid+1, low) に分けてソートします。

次にマージ処理を行います。まず前半部分を work に退避します。次の while ループで、前半部分もしくは後半部分どちらかにデータがある間、データの比較と移動を繰り返し行います。前半部分と後半部分を先頭から順番に比較し、小さい方を区間の先頭から順番にセットしていきます。後半部分のデータが先になくなって、作業領域 work にデータが残っている場合は、最後の while ループでデータを後ろに追加します。

マージソートの実行時間は、要素数を \(N\) とすると平均して \(N \log_2 N\) に比例します。マージソートはクイックソートと同様に高速なアルゴリズムですが、実際にプログラムを作って比較してみるとクイックソートの方が高速です。しかし、マージソートは配列を単純に二分割していくため、クイックソートと違ってデータの種類によって性能が劣化することはありません。