2010 年度「計算数学」 2011-01-21

§49 マージソート

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

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

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

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

を満たしているようにする。

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

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

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

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

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

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

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

§50 課題ではない

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

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

(50.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[ ] にコピーするもの。ヒントは二つめと同じ。

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

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

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

(50.7) しかし、配列 a[ ] の要素が配列 b[ ] にコピーされる回数はカウンタをつけて数えることができる。変数 scount をそれに流用すればよいだろう。交換を行なう関数 swap() ではコピーを三回行なっていたことを考えると、コピーの回数も、クイックソートより少ないようである。ただし、(48.5) に書いたようにクイックソートを改良すると、クイックソートのほうが少ないかもしれない。（b[ ] をそっくりそのまま a[ ] にコピーする部分は、上述のように、プログラミングについてもう少し学ぶと回避できるので、コピーの回数に数えない。）

§51 まとめ

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

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

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

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

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

補足：ヒープソートに、もう少し多くの情報を出力させてみよう

ヒープソートは、(41.10) に書いたように、第一段と第二段からなるのだった。 main() の最後においている比較回数・交換回数の出力を、第一段と第二段の間にも入れれば、第一段の比較回数・交換回数がわかる。差をとることで、第二段の比較・交換回数もわかる。（あるいは、第一段の出力後にカウンタに 0 を代入すれば、第二段だけの結果を出力させることができる。）

また、main() の前で

int k1count = 0;    /* 左の子のみの場合 */
int k2count = 0;    /* 左右に子がいる場合 */

と変数を宣言し、関数 heapsort() の中のしかるべき位置に「k1count++;」「k2count++;」を置くと、左の子のみの場合、左右に子がいる場合がそれぞれ何回あったかを、数えることができる。これも出力してみよ。

おまけのクイズ：数列の一部の、前後を入れ替える関数

これは、問題も答えも有名なものである。答えは、あっと驚くほど簡単なもの。

配列 a[ ] に何かデータが格納されているとする。関数 void move(int i, int j, int k) で、 a[i] から a[j-1] までと a[j] から a[k-1] までとを、それぞれの中での順序は保って、入れ替えるものを書け。

たとえば a[i] に i が格納されているとし、 move(2, 4, 7) を実行すると

  1  2  3  4  5  6  7  8  9 10 11 12

が

  1  4  5  6  2  3  7  8  9 10 11 12

に変わる。

ヒント：もう一つ関数を書いて、それを何度か呼び出す。

付録：センターの Linux の“裏”端末

センターの Linux の、あまり知られていない、“裏”端末を紹介する。

Ctrl+Alt+F1 で“裏”端末に表示が切り替わる。ログインプロンプトが出ているので、この実習用アカウントのアカウント名・パスワードでログインする。プロンプトの出ているところで Ctrl+D を押せばログアウトできる。ログインしたままで次に述べるように“表”に戻ることもできるが、シャットダウンする前には、“裏”端末のほうはログアウトしておくほうがよい。

“表”に表示を戻すのは、Ctrl+Alt+F7 である。

Linux を使っていて画面全体がまったく動かなくなってしまった場合、この“裏”端末からログインして、ある方法で正常に戻すことができる場合がある。

具体的には、悪さをしているプロセスを kill することになる。そのやり方は、簡単には説明できないので、センターの人を呼んできてお願いすることになるだろう。

岩瀬順一