2016 年度「計算数学」 2016-11-18

§6.1 素朴なソート

(6.1.1) ソートの「アルゴリズム」について考えてみよう。「アルゴリズム」とは，問題を解くための手順をあいまいさのないように書いたもののことである。

(6.1.2) まずは，「素朴なソート」を考える。これは特定のアルゴリズムの名前ではなく，プログラミングの経験を少し積んだ人がちょっと考えれば思いつくものを呼ぶ，一般的な名前である。

§6.2 ソートのアルゴリズムの良し悪し

(6.2.1) ソートのアルゴリズムの良し悪しは，比較回数（＝配列の中の二つの要素を比較する回数），交換回数（＝配列の中の二つの要素の互換を行なう回数）を配列の大きさ N の関数とみなして判定する。少ない回数で済むほうがよいアルゴリズムである。

(6.2.2) オーダーを表すオミクロン記法を復習しよう。ここでは N→∞ のときだけを考える。 N の関数 f(N) と g(N) があって，「N→∞ のとき |f(N)/g(N)| は有界」なら， f(N) = Ο(g(N)) と書き，「f(N) のオーダーは g(N) のオーダー以下である」などと言う。たとえば N(N-1)/2 = Ο(N²) である。

(6.2.3) アルゴリズムの良し悪しを論ずる際には，必要な回数を配列の大きさ N の関数とみなしたときのオーダーがまず第一に問題となる。オーダーが同じ場合は係数が次の問題となる。すなわち，同じ Ο(N²) であった場合には， N²/4 のほうが N²/2 よりも優れたアルゴリズムとなる。

(6.2.4) Ο(N log(N)) のアルゴリズムは Ο(N²) のアルゴリズムでもあるわけだが，わざわざ悪く言うこともないのでそれを「Ο(N²) のアルゴリズム」と呼ぶことは滅多にない。

(6.2.5) 比較回数と交換回数とでオーダーが違うこともあるが，その場合はオーダーの大きいほうが全体のオーダーを決めることになる。たとえば， Ο(N²) である関数 N²/2 と Ο(N) である関数 N とを足した N²/2 + N が Ο(N²) ではあるが Ο(N) ではないように。

§6.3 素朴なソートの例（その１） --- 挿入ソート【課題１】

(6.3.1) 挿入ソートは，次の原理で配列をソートする。

ソート開始時点で，a[1] から a[1] まではソートされている。（これは事実を確認しただけであり，何らかの操作を行なうわけではない。「--」はまだ調べていないという印である。）

48 -- -- -- -- -- --
a[1] から a[i-1] まではソートされているとき， a[i] をしかるべき位置に挿入して， a[1] から a[i] までがソートされているようにする。

03 05 48 92 13 -- --

↓

03 05 13 48 92 -- --

（ここでは i は 5 である。元の a[3], a[4] はそれぞれ一つずつ右にずらした。）

(6.3.2) 図書カード --- 数学教室図書室にもあるような，図書室で蔵書を検索する際に使うカード --- が（たとえば）著者名順に並んでいるところへ，新しく到着した本のカードを追加するときは，まさにこの二段目を行なうことになるだろう。すなわち，すでに並んでいるカードを新しいカードがはいるべきところで二組に分け，そこに新しいカードを挿入することになる。

(6.3.3) 図書カードのときは，新しく挿入したカードよりも「大」なるカードはカード一枚の厚みの分だけ奥にずれる。しかし，コンピュータではそう簡単にはいかないので，次のように行なう。

(6.3.4) つまり，二段目の各ステップ（＝ a[i] を挿入するステップ）は

a[i-1] と a[i] とを比較し，逆転していたら交換する。
a[i-2] と a[i-1] とを比較し，逆転していたら交換する。
...
a[1] と a[2] とを比較し，逆転していたら交換する。

とする。ただし，逆転していなかったらそこで打ち切る。そこが挿入すべき位置だから。

(6.3.5) 上の例ではこうなる。

`03`	`05`	`48`	`92`	`13`	`--`	`--`
↓
`03`	`05`	`48`	`13`	`92`	`--`	`--`
↓
`03`	`05`	`13`	`48`	`92`	`--`	`--`

次に 05 と 13 とを比較するが，ここは逆転していないので，これで操作は終わりである。その先の比較はする必要がない。

(6.3.6) 極めて重要なヒント： for ループを使い，継続条件を「j > 1 かつ a[j-1] が a[j] より大きい限り」とする。「かつ」はＣ言語では && と書くのだった。

(6.3.7) そして，これを，i が 2 から N まで， i の値を一つずつ大きくしながら行なってゆく。だから，for ループは二重になる。

(6.3.8) 初めからソートされていた場合が最も lucky な場合であり，比較回数は N-1, 交換回数は 0 である。逆順にソートされていた場合が最悪の場合であり， a[i] を挿入する際の比較回数・交換回数はどちらも i-1 となって，全体ではどちらもおよそ N²/2 となる。平均的な場合には， a[i] を挿入するときの比較・交換回数（の期待値）はどちらもおよそ i/2 であろう。よって，全体では，比較・交換回数ともに最悪の場合の半分，すなわち N²/4 とみてよいだろう。どちらもΟ(N²) である。以下に述べる二つのアルゴリズムとは異なり，もしも配列がほとんどソートされていれば比較回数も交換回数も小さいことに注意しよう。

§6.4 課題１

(6.4.1) 前からの準備を元にして，以下のヒントを読みつつ，乱数列で初期化された配列を挿入ソートでソートするプログラムを書け。そして，メールでレポートせよ。ファイル名は insert.c がよいかも知れない。（英語では insertion sort と呼ばれるらしい。）

(6.4.2) 元にするのは，前回書いた， swap() と comp() を付け加えたソースファイルである。これらの関数のテスト用として main() に書き加えた部分は削除しておく。

(6.4.3)

#include ...

main() {
    ...

    for (i = ?; i <= ?; i++) {
        printf("いまから a[%d] を挿入します.\n", i);   /* a[] の値も出力する？ */
        for (j = ?; j ? ? && ???; j??) {
            ...
            swap(?, ?);
            print();            /* これを (6.7.2) の print2() に変えてみよ */
        }
    }
}

まずは，配列の大きさを 8 から 10 程度とし，プログラムを完成する。このときは swap() を呼ぶごとに print() を呼び，配列全体を画面に出力させる。途中で「いまから a[5] を挿入します.」）のようなメッセージを出すのは，出力結果に区切りを入れて見やすくするためである。

(6.4.4) 次に，配列の大きさを 60 にし，次のように書き足して，比較回数，交換回数を調べる。

#include ...

int ccount = 0;     /* 比較（comp()）のカウンタ。0 で初期化 */
int scount = 0;     /* 交換（swap()）のカウンタ。0 で初期化 */

main() {
    int i, j;

    printf("配列の大きさは %d です.  ", N);     /* 配列の大きさを出力 */
    printf("…………田中美佐子\n", N);          /* 自分の氏名を出力 */
    init();

    /* ここは上で書いた二重ループによるソートの部分 */

    printf("%d 回比較しました.\n", ccount);     /* 比較回数を出力 */
    printf("%d 回交換しました.\n", scount);     /* 交換回数を出力 */
}


void swap(int i, int j) {
    ...

    scount++;   /* ここを通るたびにカウンタが増える */
}


int comp(int i, int j) {
    ccount++;   /* ここを通るたびにカウンタが増える */

    return a[i] - a[j];
}

関数 comp() が呼び出されるたびに変数 ccount の値が増されるので，これで comp() が呼び出された回数がわかる。変数 scount についても同様。これで，比較回数・交換回数が (6.3.8) に書かれた値に近いことを確認する。

(6.4.5) 違っていたら，前に戻ってやり直し。もしも，正しくソートされるが理論上の回数の二倍近い回数になっていて直し方がわからない場合，私を呼べ。

(6.4.6) ここまでできたら，print() の呼び出しを「/*」と「*/」で囲んでコメントにし，配列の出力はいっさい行なわないようにする。「いまから ... を挿入します.」の出力も同様にコメントとする。なお，この授業で使っているコンパイラは実は C++ コンパイラなので， C++ でのコメントの記号，すなわち「//」を使ってもよい。これを書くと，そこから行の終わりまでがコメントになる，という約束である。このときの出力は次のようになる。配列の大きさ N をいくつに選ぶかは，下を参照。

配列の大きさは .... です.  …………田中美佐子
乱数の種は .......... です.
..... 回比較しました.
..... 回交換しました.

(6.4.7) メールは，必ず，この授業で配布したアカウントから送れ。メールの本文冒頭に，学籍番号，名列番号，氏名（として大学に届けてあるもの）を忘れずに書け。次に，レポートの内容を，「挿入ソートのプログラムと実験結果」程度に，簡潔に書け。

(6.4.8) その次に，プログラムを載せよ。その際，KAINS Webmail のメール作成画面の「ファイルを添付」 *ではなく* 本文の中にソースファイルを貼りつけること。プログラムは，下に指示するように， N の値を三通りに変えてコンパイル・実行するが，載せるプログラムは N が指定のうちで最大のものとせよ。また，実験を行なったプログラムそのものでなければならない。（一部でも変更したときは，コンパイル・実行をやり直すこと。）

(6.4.9) 比較回数・交換回数を調べる際には，配列の大きさ N の値を 100, 1000, 10000 の三通りに変えること。それぞれの N について最低でも５回ずつくり返して実験せよ。その際，乱数の種が毎回異なるようにするため，一秒以内に二度以上プログラムを動かすな。また，実験は，必ず，センターの Linux 上で行なうこと。

(6.4.10) 実験結果すべて（最低でも１５回分）を，まとめてコピペして送れ。すなわち，プロンプトや「./a.out」，「cc insert.c」を含んだままコピペせよ。（編集すると間違うおそれがあるため。）

(6.4.11) 上で書くよう指示したこと以外は書かなくてよい。感想などは書かなくてよい。書きたければ書いてもよい。

(6.4.12) 宛て先は私（岩瀬）の実習用アカウント（(1.9.7) 参照）である。件名は「?? kadai1」（←全て半角文字， ?? は自分の id の下二けた，その後ろに半角スペース一つ， kadai は小文字， kadai と 1 の間にはスペースを入れない）とせよ。

(6.4.13) 出されたレポートは，なるべく早く採点し，必ず返事をメールで送る。そこに「OK」と書かれていて初めて，その課題の点数を得たことになる。「やり直し！」の場合，「OK」になるまで，訂正・加筆して，再提出せよ。何回再提出しても，最後に「OK」になれば，一度で「OK」になった人と同じ得点を与える。なお，再提出の場合も，「あたかもそれが最初の提出であるかのように」書け。（訂正箇所だけを送るのは不可。最初のメールを「転送」するのも不可。）

§6.5 偏った初期化をする関数

(6.5.1) ここは，時間などに余裕がある人のためのオプション項目である。

(6.5.2) 配列 a[ ] を初期化する際，わざと偏ったやり方で行なったら，比較回数，交換回数はどうなるだろうか？　「a[i] = i;」と書けば元々データはソートされていたことになる。「a[i] = N + 1 - i;」なら逆順。「a[i] = i + rand() % 5;」とすれば「だいたいそろっているが完全にはソートされていないデータ」になる。（5 という数に特別な意味はない。）

§6.6 ソートが完了したことをチェックするルーチン

(6.6.1) ここは，時間などに余裕がある人のためのオプション項目である。

(6.6.2) 本当にソートできたかどうかチェックするルーチンをつけてみよう。配列 a[ ] に 0 が代入されていないこと，および， a[1] が a[2] 以下であること， a[2] が a[3] 以下であること， ………， a[N-1] が a[N] 以下であること，を順にチェックすればよい。違っていたらメッセージを画面に出力させる。独立した関数にしてもよいし， main() の最後に置いてもよいだろう。

(6.6.3) ※ 「a[i] = rand();」のほうで初期化する際， a[i] に 0 が代入されることがありえるから，配列に 0 が代入されていたからといってプログラムが間違っているとはいえない。しかし，N は RAND_MAX（(5.2.4) 参照）よりずっと小さいので， 0 が代入される可能性はかなり低い。

§6.7 画面出力関数の改良（その１）

(6.7.1) ここは，時間などに余裕がある人のためのオプション項目である。

#include <stdio.h>

main() {
    int x;

    x = 123;
    printf("\033[41m%d\033[m\n", x);    /* 赤 */
    printf("\033[42m%d\033[m\n", x);    /* 緑 */
    printf("\033[43m%d\033[m\n", x);    /* 黄 */
    printf("\033[44m%d\033[m\n", x);    /* 青 */
    printf("\033[45m%d\033[m\n", x);    /* マゼンタ */
    printf("\033[46m%d\033[m\n", x);    /* シアン */
}

これは，Ｃ言語ではなく，ここの端末の話である。いままでは白い文字を出力するだけだったが，ここの端末は，\033 で始まる特別な文字列を出力することで，文字の色などを変えることができる。 \033[41m で地が赤になる，\033[m で元に戻る。

(6.7.2) 配列の要素の値を画面に出力するが，特定の a[i], a[j] だけを特別の地色で画面に書く関数， void print2(int i, int j) を書け。

(6.7.3)

        swap(i, j);
        print2(i, j);

このように使えば，交換された要素だけが特別な地色で表示され，アルゴリズムの理解を助けてくれるだろう。その際，配列の大きさは画面いっぱいにすると見ていておもしろい。なお，端末の「スクロールバックのサイズ」を「無制限にする」にしておくこと。

(6.7.4) ※　この授業で扱うプログラムは，ほぼすべてのＣコンパイラを通るはずである。諸君の必携パソコンにはいっている gcc でコンパイルし，実行可能だと思う。それに対し，上のように出力の色を変えるのは，端末がそれに対応していなければ使えない。

(6.7.5) さらに画面制御エスケープシーケンスについて知るには，ネットで検索してみてほしい。

§6.8 画面出力関数の改良（その２）

(6.8.1) ここは，時間などに余裕がある人のためのオプション項目である。

(6.8.2) 画面制御エスケープシーケンスを利用し，次のようなスタイルで配列の要素を画面に描く関数 void print3(void) を作ってみよう。

#####
###
#######
#########

これは a[1] が 5, a[2] が 3, a[3] が 7, a[4] が 9 を示す。「#」の数で要素を表しているのである。

void print3(void) {
    int i, j;

    printf("\033[1;1H");  /* 左上隅に移動する */
    for (i = 1; i <= N ; i++) {
        /* ここで a[i] 個の「#」を出力 */
        printf("\033[K"); /* 行末まで削除 */
        printf("\n");     /* 次の行へ移動 */
    }
}

§6.9 素朴なソートの例（その２） --- バブルソート

(6.9.1) 「a[i] > a[i+1] を満たす i があったら a[i] と a[i+1] とを交換する。これをくり返してゆく」というのがこのソートのアイディアである。幼稚園の先生が園児を背の順に並ばせるとき，この方法を採用することもあるだろう。そのような i のさがし方はいろいろ考えられる。（そのうちのどれを採用するかをきちんと述べるまでは，これをアルゴリズムとは呼べない。）

(6.9.2) 次に示すのはその一つのやり方である。

a[1] と a[2] を比較し，逆転していたら交換する。
a[2] と a[3] を比較し，逆転していたら交換する。
...
a[N-1] と a[N] を比較し，逆転していたら交換する。

これで，最大の値をもつもの（のうちの一つ）が a[N] にはいることを（頭の中で）確かめよ。（幼稚園の先生が園児を背の順に並ばせる過程でいえば，どんな手順をとったことになるか？）

次に

a[1] と a[2] を比較し，逆転していたら交換する。
a[2] と a[3] を比較し，逆転していたら交換する。
...
a[N-2] と a[N-1] を比較し，逆転していたら交換する。

これで，a[1] から a[N-1] までのうちで最大のもの（＝配列全体で言えば二番目に大きいもの）が a[N-1] にはいった。以下はこれのくり返し。

(6.9.3) このアルゴリズムでの比較回数は (N-1) + (N-2) + ... + 2 + 1 = N(N-1)/2, すなわち，およそ N²/2 である。交換回数は最悪の場合（＝完全に逆順に並んでいた場合）が比較回数と同じ，最も lucky な場合（＝元々ソートされていた場合）が 0 で，平均するとおよそ N²/4 とみてよいだろう。よって，全体では Ο(N²) のアルゴリズムである。

(6.9.4) 興味のある人はこのアルゴリズムでソートを行なうプログラムを書いてみよ。

§6.10 素朴なソートの例（その３） --- 単純選択法

(6.10.1) a[1] から a[i] までのうちで最大のもの（の一つ）の添え字を求める操作を i-1 回の比較で行なう方法が存在する。このことは容易だから認めよう。

(6.10.2)

a[1] から a[N] までで最大のものを a[N] と交換する。
a[1] から a[N-1] までで最大のものを a[N-1] と交換する。
...
a[1] から a[3] までで最大のものを a[3] と交換する。
a[1] から a[2] までで最大のものを a[2] と交換する。

これでソートが完了する。

(6.10.3) 全体の比較回数は (N-1) + (N-2) + ... + 1 = N(N-1)/2 回，交換回数は N-1 回である。（最大のものが最後にきていても，すなわち，交換の必要がなくても swap() を呼び出すほうが全体としては速い。よって，交換回数は「たかだか N-1 回」ではなくちょうど N-1 回である。）

(6.10.4) 以上から，このソートの比較回数は Ο(N²) であり，交換回数は Ο(N) であることがわかる。全体では Ο(N²) のアルゴリズムである。

(6.10.5) 興味のある人はこのアルゴリズムでソートを行なうプログラムを書いてみよ。

(6.10.6) ※ a[1] から a[i] までのうちで最大のもの（の一つ）の添え字を求める際には， j < i なる j に対し a[1] から a[j] までで最大の値を持つもの（の一つ）の添え字を保持しておくわけだが，より速いプログラムを書くなら，そこまでの最大値そのものも保持しておくほうがよい。ただし，こうすると，前に書いた関数 comp() は使わないことになる。

§6.11 ほかのパソコンのＣコンパイラについて

(6.11.1) Ｃ言語は規格化されており，その規格に沿って書かれたＣプログラムはどのＣコンパイラも通るのだが， RAND_MAX の値などは規格では完全には決まっていない。ここの Linux では RAND_MAX は 2³¹-1 だが， 2¹⁵-1 になっているものもある。そういうマシンで実験を行なうと，比較回数・交換回数が違ってくる可能性があるので，注意が必要である。

岩瀬順一