2013 年度「計算数学」 2014-01-31

§11.1 マージソート

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

(11.1.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 ずつ並んでいる」と呼ぼう。（最後に半端が出たら，それらも小さい順に並んでいるとする。）

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

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

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

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

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

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

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

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

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

§11.2 課題ではない

(11.2.1) 課題ではないが，興味のある人は，マージソートのプログラムを書いてみよ。

(11.2.2) 挿入ソートのソースファイルをコピーしたものに，下のプログラムをはりつけ，ヒントに従って埋めてゆく。ファイル名は merge.c がよいだろう。

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

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();
    }
    /* ここで，いつものように比較回数の表示などを行なう */
}

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

m は，「m ずつ並んでいる」のを「2m ずつ並んでいる」に変える，その m である。最も外の for ループではこの m が変わる。
二組を一組にまとめるわけだが，その中で最も添字が小さいものが a[start] だとする。外から二番目のループでは，start を 1 から初めて，だんだん大きくしてゆく。
一番内側の三つの for ループで， a[start] から始まる 2m 個の元を小さい順に b[ ] にコピーする。
- その一つめの for ループの本体では，第一群の 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[ ] にコピーするもの。ヒントは二つめと同じ。

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

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

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

(11.2.7) しかし，配列 a[ ] の要素が配列 b[ ] にコピーされる回数はカウンタをつけて数えることができる。変数 scount をそれに流用すればよいだろう。コピーの回数を前のアルゴリズムと比べる際には，交換を行なう関数 swap() ではコピーを三回行なっていたことを思い出せ。（b[ ] をそっくりそのまま a[ ] にコピーする部分は，上述のように，プログラミングについてもう少し学ぶと回避できるので，コピーの回数に数えない。）

§11.3 ソートの安定性

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

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

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

int a[N+1]; の次の行に int b[N+1]; を追加する。（i.e. 同じ長さの配列をもう一つ用意する。）
配列を初期化する関数 init() は， a[i] はいままで通りに乱数で初期化するが， b[i] には i を代入して初期化する。
配列を画面に出力する関数 print() は， a[i] の値を一行に出力したのち， b[i] の値を次の行に出力する。（ヒープソートの場合もこれを使う。）
互換を行なう関数 swap() は， swap(i, j) を実行するとき， a[i] と a[j] の値を入れ換えるだけでなく， b[i] と b[j] の値をも入れ換える。

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

(11.3.5) 配列の大きさ N を画面の一行に収まるぐらいとし，途中の過程をすべて出力させて実験すれば，どの過程で安定性が崩れるのかをも見ることができる。

(11.3.6) 配列の大きさを大きくして試したい場合，安定かどうかを目で見て判定するのは大変であろう。 print() は呼ばないようにし， main() の最後に安定かどうかをチェックする部分をつけるとよい。 a[i] と a[i+1] が等しいときに b[i] と b[i+1] の大小関係を調べればよいから，それほどむずかしくないと思う。

(11.3.7) この授業の課題では，同じ値をもつものはないと考えてプログラムを書いてきた。そのため， comp(i, i+1) > 0 のように，関数 comp() の次には等号なしの不等号がきているであろう。そこを，等号つきの不等号で置き換えても正しいプログラムであるかどうか確認せよ。正しいならば，そのプログラムでも実験を行ない，等号なしの場合と比べて，比較・交換回数がどう変わるか調べてみよ。その際には，同じ値をもつものが多くあるほうが違いがわかりやすいので， N の値を大きくし，かつ，初期化は a[i] = rand() % 99 + 1; などとするのもよい。

§11.4 まとめ

(11.4.1) 以上で，ソートの学習は終わりとする。初めのうちは非常に自明なプログラムを学び，突然，初心者にはかなり高度といえる，非自明なアルゴリズムに基づくプログラミングを学んだことになるが，諸君の多くが，粘り強く課題に取り組んでくれたと思う。その粘り強さを，今後，数学や物理学の勉強に生かしてほしい。

(11.4.2) 興味のある人は，取り上げたうちの，計算量が Ο(N log(N)) のアルゴリズム --- ヒープソート，クイックソート，マージソート --- について，配列の大きさ N をさらにいろいろな値に変えて実験し， N を大きくするとき N log(N) の定数倍に近づいてゆくかどうかを調べ，もしそうなっていたら，その定数の値はいくつになるか，求めてみてほしい。それが小さいほど，速いアルゴリズムということになる。そのほか，この三つのアルゴリズムにはそれぞれ長所・短所がある。まとめてみるとよいだろう。

(11.4.3) ソートのような，問題の意味を理解するだけなら簡単な問題にも，いろいろな解法があり，工夫次第でスピードを上げることができる。先人たちの研究結果を学ぶことの大切さを知ってほしい。

(11.4.4) また，いくら努力してもこえられない理論上の限界 (§7.5) がある，ということを理解するのも大切である。

(11.4.5) 数学では，可能な操作は一瞬で終わったとして先へ進む。たとえば，「この行列の固有値を小さい順に並べて λ₁ < λ₂ < ... < λ_n とします」のように。このあたりの，ものの考え方の違いについても考えてみてほしい。

岩瀬順一