2021 年度「計算数学b」 2021-12-24

§10.1 マージソート

(10.1.1) マージ (merge) ソートは、アルゴリズムは比較的わかりやすいが、 ソートすべきデータがはいっている配列 a[ ] のほかに、 それと同じ大きさの配列 b[ ] が必要となる。 (最近のコンピュータは大量のメモリーを搭載しているので、 この点はあまり問題にならないように思う。)

(10.1.2) 配列 a[ ] が次を満たしているとする。

これを(ここでは)「4 ずつ並んでいる」と呼ぼう。 (最後に半端が出たら、それらも小さい順に並んでいるとする。)

(10.1.3) このとき、この配列全体をもう一つの配列 b[ ] にコピーし、 次を満たしているようにする。

(10.1.4) 子どもたちが四人ずつ班に別れ、 それぞれの班の中では背の順に並んでいるとき、 二班を一つにまとめ、八人が背の順に並ぶようにせよ、というのと同じである。

(10.1.5) それには、次のようにすればよい。 a[1] から a[8] までの部分で説明しよう。 まず a[1]a[5] を比べ、小さいほうを b[1] にコピーする。 もしも a[1] のほうがコピーされたなら、 次には a[2]a[5] を比較する。 いわば“勝ち抜き戦”である。 片方のグループの元をすべてコピーしてしまったら、 あとはもう一つのグループの残りを(比較することなしに)順にコピーする。

(10.1.6) 配列 a[ ] 全体に対し上の操作をおこなって配列 b[ ] にコピーし終えたら、 それから、b[ ] 全体を a[ ] に、 そっくりそのまま、順序を変えずにコピーする。

(10.1.7) これで、配列 a[ ] を、 「4 ずつ並んでいる」から 「8 ずつ並んでいる」に変えることができた。

(10.1.8) 最初に配列 a[ ] を乱数で初期化した直後には、 この配列は「1 ずつ並んでいる」と言える。 それを上のような操作で「2 ずつ並んでいる」ように変え、 「4 ずつ並んでいる」ように変え、 ……とくりかえしてゆけば、やがて配列全体がソートされる。 このアルゴリズムを「マージソート」という。

(10.1.9) m ずつ並んでいる m 個のもの二組を小さい順に並べて別の場所にコピーする際、 次にコピーすべき元(げん)を決めるには、たかだか一回の比較で済む。 最後の一つは、残ったものだから、比較しなくても決まる。 よって、比較回数はたかだか 2m-1 回である。 コピーされる元は 2m 個である。 これらはおよそ 2m である。 よって、 「m ずつ並んでいる」から「2m ずつ並んでいる」に変えることは およそ N の計算量で可能である。 これを全部で約 log2(N) 回くりかえすから、 全体では N log(N) である。

(10.1.10) 前にとりあげたクイックソートとは異なり、 初めに配列がどのように初期化されていても、このオーダーである。 また、乱数で初期化する場合、平均すると、 クイックソートよりも比較回数は少ないようである。

§10.2 課題5

(10.2.1) 課題2と同様のことを、マージソートについておこなえ。

(10.2.2) 挿入ソートのソースファイルをコピーしたものの main() から挿入ソートの二重ループを削除し、 下のプログラムのヒントに従って書き換えてゆく。 ファイル名は merge.c がよいだろう。

(10.2.3) プログラムの main() は次のようになる。

int main() {
  int m, start, i, j, k;

  /* ここで、いつものように、配列の大きさの表示、配列 */
  /* の初期化、初期化直後の配列の画面表示をおこなう   */

  for (m = 1; m ???; m = ???) {
    printf("「%d ずつ並んでいる」のを", m);
    printf("「%d ずつ並んでいる」ように変えます.\n", 2*m);
    for (start = 1; start ???; start = ???) {
      i = 0; j = 0; k = 0;
      for (    ; ????????????????????????????????;   ) {
        if (comp(start+i, start+m+j) < 0) {
          b[???] = a[???];
        } else {
          b[???] = a[???];
        }
      }
      for (    ; ??????????????????????;   ) {
        b[???] = a[???];
      }
      for (    ; ??????????????????????;   ) {
        b[???] = a[???];
      }
    }
    /* ここで、for ループを用いて、配列 b[ ] を */
    /* 配列 a[ ] にそっくりそのままコピーする   */
    print();
  }
    /* ここで、いつものように比較回数の表示などをおこなう */
}

変数は、上のように、五つ用意する。

(10.2.4) 「int a[N+1];」の次の行に「int b[N+1];」を入れるのを忘れずに。

(10.2.5) ※ 実は、b[ ] をそのまま a[ ] にコピーして戻すのは時間の無駄である。 その際、ついでに「2m ずつ並んでいる」のを 「4m ずつ並んでいる」ように変えれば、 この無駄が省ける。 しかし、プログラムが長くなるか、まだ習っていない書き方が必要になる(と思う)。 また、配列の要素を一つずつコピーするのではなく、 まとめて効率よくコピーするための備えつけの関数 memcpy() があるが、この授業ではふれない。

(10.2.6) いままでのアルゴリズムとは異なり、要素の交換のくり返しではないから、 関数 swap() は使わない。よって、交換回数は調べない。 (関数 swap() や変数 scount は使わないが、残しておいて構わない。)

(10.2.7) プログラムを書いている間は、 配列の大きさ N を 15, 16, 17 など、いろいろに変えて試すこと。 半端の処理もきちんとできているか、の確認のためである。

(10.2.8) 件名は「?? kadai5」(←全て半角文字、 ?? は自分の id の下二けた、その後ろに半角スペース一つ、 kadai は小文字、 kadai5 の間にはスペースを入れない)とせよ。 これ以外の注意点は課題2と同じである。

(10.2.9) N の値を大きくしての実験は、 N を 10000, 100000, 1000000 にして、五回ずつおこなえ。

(10.2.10) 付記: a[i]b[j] にコピーする関数 void copy(int j, int i) を作り、その中でカウンタを増やすことでコピーの回数を調べることもできるが、 コピーの回数は N の大きさで決まる定数になる。考えてみよ。 なお、上のプログラムでは、配列 b[ ] から配列 a[ ] へのコピーもあるので、実際のコピーの回数はその 2 倍である。 (関数 swap() を使う場合、その中で 3 回のコピーをおこなっているので、 コピーの回数は交換回数の 3 倍である。)

§10.3 ソートの安定性

(10.3.1) この節は、課題が早く終わって時間が余った人のためのものである。 前に (5.3.3) で述べた、 ソート前のデータに同じ値のものがあった場合の問題を考えよう。

(10.3.2) あるソートのアルゴリズムが「安定 (stable)」であるとは、 同じ値のものが、ソート後も元の順序を保っていることをいう。 あるソートアルゴリズムが安定であることをいうには、 数学の定理と同様に証明が必要であり、 不安定(あるいは非安定)であることをいうには反例をもって示すべきであるが、 実験で試し、その結果を参考にすることができる。

(10.3.3) この授業で書いているプログラムを少し改変することで、 その実験がおこなえる。以下では、そのやり方の一つを説明する。 プログラムのコピーを、次のように改変する。

(10.3.4) 以上のように改変してから実行する。 ソート後、a[i] の値が同じものが並んだら、 それらの中で b[i] の値が小さい順かどうかを調べる。

(10.3.5) a[i] の中に同じ数のものが多く出たほうが便利なので、 初期化する乱数の値を 1 から 99 まででなく、 もっと小さな数まで、とすることも考えられよう。


岩瀬順一