2009 年度「計算数学１」 2009-05-11

§56 マージソート

(56.1) マージ (merge) ソートでは、ソートすべきデータがはいっている配列 a[ ] のほかに、それと同じ大きさの配列 b[ ] が必要となる。そこが欠点であるが、アルゴリズムは比較的わかりやすい。

(56.2) 配列 a[ ] が

a[1] から a[4] までは小さい順（i.e. a[1] ≦ a[2] ≦ a[3] ≦ a[4])、
a[5] から a[8] までは小さい順（i.e. a[5] ≦ a[6] ≦ a[7] ≦ a[8])、
……

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

(56.3) このとき、この配列全体をもう一つの配列 b[ ] にコピーし、

b[1] から b[8] までは a[1] から a[8] までを小さい順に並べたもの、
b[9] から b[16] までは a[9] から a[16] までを小さい順に並べたもの、
……

を満たしているようにする。それには、次のようにすればよい。

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

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

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

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

(56.8) m ずつ並んでいる m 個のもの二組を小さい順に並べて別の場所にコピーすることは、 Ο(2m) の計算量で可能である。よって、「m ずつ並んでいる」から「2m ずつ並んでいる」に変えることは Ο(N) の計算量で可能である。これを全部で log(N) 回くりかえすから、全体では Ο(N log(N)) である。

§57 課題６

(57.1) 課題５と同様のことを、マージソートについて行なえ。メールの件名は「kadai6」とせよ。

(57.2) いままでのアルゴリズムとは異なり、要素の交換のくり返しではないから、関数 swap() は使わない。よって、交換回数は調べない。（関数 swap() や、最後の交換回数の出力の printf() 文は残しておいて構わない。）

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

(57.4) 変数は、下のように、五つ用意する。

m は、「m ずつ並んでいる」のを「2m ずつ並んでいる」に変える、その m である。最も外の for ループではこの m が変わる。
二組を一組にまとめるわけだが、その中で最も添字が小さいものが a[start] だとする。外から二番目のループでは、start を 1 から初めて、だんだん大きくしてゆく。
三つめの for ループでは、 a[start] から始まる 2m 個の数を小さい順にして b[ ] にコピーする。このループの本体内では、第一群の a[start+i] と第二群の a[start+m+j] を比較し、小さいほうを b[start+k] にコピーする。
- この for の初期設定は、i, j, k に 0 を代入するものである。一つにまとめて for の小カッコの中に入れる方法もあるが、ここではそこは空白とし、for の一行前に書いた。
- この for の継続条件は、 i, j がしかるべき範囲にあり、かつ、添字 start+i, start+m+j, start+k が配列の終わりを越えていないことである。（よって、いくつかの条件を && でつなぐことになる。五つすべてが必要なわけではない。）
- この for の再初期化は、必要に応じて i, j, k を 1 だけ増すことである。どれとどれを増やすかは、場合によって異なるので、 for の小カッコの中に入れるのはむずかしい。そこで、for の小カッコの中の三番めは空白にしておき、ループ本体内の適当なところに「i++;」などを置く。（その場所は下のヒントでは示していない。自分で考えること。）
四つめの for ループは、第一群の残りを b[ ] にコピーするもの。初めて使うテクニックだが、その前の for ループを抜けたあとの i, k の値をそのまま使う。よって、この for の初期設定は空白である。再初期化も空白とし、「i++;」などはループ本体の適当なところに置く。
五つめの for ループは、第二群の残りを b[ ] にコピーするもの。ヒントは四番めと同じ。

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

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

    for (m = 1; m ???; m = ???) {
        printf("「%d ずつ並んでいる」のを「%d ずつ並んでいる」ように変えます.\n", m, 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[???];
            }
        }
        /* ここで、配列 b[ ] を a[ ] にそっくりそのままコピーする */
        print();
    }
    /* ここで、いつものように比較回数の表示などを行なう */
}

(57.5) ※ 実は、b[ ] をそのまま a[ ] にコピーして戻すのは時間の無駄である。その際、ついでに「2m ずつ並んでいる」のを「4m ずつ並んでいる」ように変えれば、この無駄が省ける。しかし、プログラムが長く煩雑になるか、まだ習っていない書き方が必要になる（と思う）。

岩瀬順一