2017 年度「計算数学ａ」 2017-11-17

§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.7, §6.8 で述べる二つのアルゴリズムとは異なり，もしも配列がほとんどソートされていれば比較回数も交換回数も小さいことに注意しておこう。

§6.4 課題１

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

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

(6.4.3)

#include ...

int main() {
    ...

    for (i = ?; i <= ?; i++) {
        printf("いまから a[%d] (= %02d) を挿入します.\n", i, a[i]);
        for (j = ?; j ? ? && ???; j??) {
            ...
            swap(?, ?);
        }
    }
}

...

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

    print();    /* 画面表示 */
}

初期化したのちは，配列 a[ ] に収められた値は，関数 swap() によってのみ変更する。すなわち，a[i] = a[i+1] などとは書かない。プログラムを完成させるまでは，関数 swap() で値が入れ替わるごとに配列の値すべてを表示させたいので， swap() の中で print() を呼び出す。このときは，配列の大きさは 10 程度でよい。途中で「いまから a[5] (= 48) を挿入します.」）のようなメッセージを出すのは，出力結果に区切りを入れて見やすくするためである。

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

#include ...

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

int main() {
    int i, j;

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

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

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


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

    print();    /* 画面表示 */
    scount++;   /* ここを通るたびにカウンタが増える */
}


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

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

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

(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 について最低でも５回ずつくり返して実験せよ。その際，乱数の種が毎回異なるようにするため，一秒以内に二度以上プログラムを動かすな。また，実験は，必ず，センターのパソコンでおこなえ。

(6.4.10) 実験結果すべて（最低でも 15 回分）を，まとめてコピペして送れ。すなわち，プロンプトや「a」，「gcc insert.c」を含んだままコピペせよ。これは編集すると間違うおそれがあるためである。なお，cmd からコピーする際には，範囲指定したのち， Ctrl+C を押す。

(6.4.11) 感想などは書かなくてよい。書きたければ書いてもよい。

(6.4.12) 宛て先は私（岩瀬）の実習用アカウント（(1.8.8) 参照）である。件名は「?? 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 + myrand() % 5;」とすれば「だいたいそろっているが完全にはソートされていないデータ」になる。（5 という数に特別な意味はない。）

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

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

(6.6.2) ※ 「a[i] = myrand();」のほうで初期化する際， a[i] に 0 が代入されることがありえるから，配列に 0 が代入されていたからといってプログラムが間違っているとはいえない。しかし，N は myrand() の返す乱数の最大値 1073741823 よりずっと小さいので，0 が代入される可能性はかなり低い。

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

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

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

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

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

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

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

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

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

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

岩瀬順一