2014 年度「計算数学」 2014-10-30

§5.1 整列（ソート）とは

(5.1.1) この授業の前半のテーマである「整列」にはいる。 

 88 98 20 82 31 53 22 10 12 91 92 79 95 50 19 58

整列とは，上のような有限数列が与えられたとき， それらを小さい順に並べかえることである。 整列は「ソート (sort)」とも言う。 ただし，「整列」「sort」の日常用語としての意味は少し違う。

(5.1.2) ※ 実際の仕事でコンピュータを使う際には， 数だけを並べかえたのでは意味がないのが普通である。 たとえば， 受験者一人一人に対応するデータ 「受験番号，国語の得点，数学の得点，英語の得点，合計点」 の組が受験者の数だけあり，それらを合計点の順に並べかえる， というような操作をすることが多いであろう。 これから考えるのは，（いわば）合計点だけを並べかえるもので， 実地にはあまり役立たない。 また，Excel （エクセル）などの表計算ソフトはソート機能を持っているので， 応用上はそれらを使えばよい。

(5.1.3) ※ 同じ値があった場合にどちらを先にもってくるかは， 「どちらでもよい」としておく。

実用上は，問題になる場合がある。 昔，試験のあと， 成績優秀者の氏名と得点を掲示したことがあった。 名簿の順に並んでいるデータを得点順に並べかえて上から何人かを選ぶのだが， もしも同点の学生がいた場合は左のように名簿の順にしておくのが普通である。 

    100 点 伊藤＊，田中＊＊，藤村＊＊        100 点 藤村＊＊，伊藤＊，田中＊＊

     95 点 ...                                95 点 ...

そうではなく，右のように書いたとすると 「同じ 100 点だけど藤村君が先頭にきているのは何か理由があるのかな」 と思われるのでうまくないかもしれない。

§5.2 ソートプログラムの準備

(5.2.1) 次のプログラム例を見ながら， 以下の説明を読むこと。 このプログラムは完全ではないので， 指示に従って自分で書き加える必要がある。 長いので，コピペすることを強くすすめる。

「自分の氏名を出力」の部分は， 「田中美佐子」を自分の氏名に変えること。 （これは，採点時の便宜のために入れてもらうものである。） 

#include <stdio.h>
#include <stdlib.h> /* rand(), srand() */
#include <time.h>   /* time() */

#define N 10

void init(void);
void print(void);

int a[N+1];     /* これで a[1] ... a[N] が使える。a[0] は使わない */

main() {
    printf("配列の大きさは %d です.  ", N);     /* 配列の大きさを出力 */
    printf("…………田中美佐子\n");             /* 自分の氏名を出力 */
    init();                                     /* 初期化 */
    print();                                    /* 画面表示 */
}


void init(void) {
    int i;

    {   /* この中カッコの中（乱数の種の設定）はわからなくてもよい */
        unsigned seed = (unsigned)time(NULL);   /* 現在時刻を取得して */
        printf("乱数の種は %u です.\n", seed);
        srand(seed);                            /* それを乱数の種に */
    }

    a[0] = 0;                       /* 念のためこうしておく */

    if (N < 70) {                   /* N が小さいとき */
 
            /* ここを各自で埋めよ */

    } else {                        /* N を大きくして実験するとき */
        for (i = 1; i <= N; i++) {
            a[i] = rand();
        }
    }
    return;                         /* この return は普通は書かない */
}


void print(void) {
    /* このコメントは消して，ここに関数 print() の本体を書く */
}

(5.2.2) 数列は，int 型の配列 a[ ] に入れる。 その大きさ N は， 容易に変えられるよう， #define を使って書いた。

(5.2.3) Ｃ言語の配列は添え字が 0 から始まるので，普通は a[0] から a[N-1] までを使うことになるが， わかりやすくするため a[1] から a[N] までを使いたい。 それには， 「int a[N+1];」と宣言することで a[0] から a[N] までを用意し， 最初の一つ，a[0] は使わなければよい。

(5.2.4) 初めに，init() という自作関数でこの配列を「初期化」する。 初期化とは，一般には初めのデータを代入することである。 ここでは乱数で初期化する。

(5.2.5) 「void init(void) {」で始まっているが， 最初の void はこの関数が値を返さないことを示す。 値は返さないがある働きをする，という関数である。 小カッコの中の void は，引数がないことを示す。 使うときは「init();」のように使う。 小カッコの中には何も書かない。 すでに出てきた rand() がそうだった。

(5.2.6) N の値によって初期化を変える理由を， 以下で説明する。

(5.2.7) 考えながらプログラムを書いている間は，N の値を小さくとり， ソートの過程で何度か配列の値を全て出力して， ソートが進んでいることを確認する。 この段階では， 配列を初期化する際に代入する値は 100 未満で十分だし， そのほうが画面上での大小の比較が容易である。 また，あとで説明するが， これらの値は 1 以上としておくほうが， プログラムの間違いを見つけやすい。 以上から，値の範囲は 1 以上 99 以下としよう。

(5.2.8) プログラムが完成したら， N の値を何百万，何千万と大きくしての実験も行なう。 その際には， 同じ値で初期化された項がたくさんあるとうまくないので， 値の範囲は広ければ広いほどよい。 よって，配列には乱数の値をそのまま代入し， 値の範囲を 0 以上 RAND_MAX 以下とする。

(5.2.9) 上の init() の， 「N が小さいとき」の部分を各自で書け。

(5.2.10) プログラムの末尾にある関数 print() の本体を書け。 この関数は，配列に格納されている値を (5.1.1) に示したようなスタイルで， すなわち，スペースで区切って一行に出力し，最後に改行するものとする。 数が一桁のときも二桁分の幅に出力されるようにせよ。 そのとき，十の位を 0 とするかスペースにするかは各自の趣味にまかせる。 （printf() の中で， %d の代わりに %02d または %2d と書けばよい。）

(5.2.11) main() では init() と print() を続けて呼んでいるだけなので， 起動するたびに異なる乱数列が表示されるプログラムができたはずである。 （非常に短い間隔で起動すると，同じ乱数列になることもある。）

§5.3 互換を行なう関数 swap()

(5.3.1) ソートプログラムの多くは， 互換， すなわち配列の二つの要素の交換からできている。 そこで，まず，互換を行なう関数を書こう。

(5.3.2) §5.2 で完成させたプログラムに， 関数 void swap(int i, int j) を書き加えよ。 この関数は， 要素 a[i] と a[j] の値を入れかえるものとする。 i と j が正しい範囲にあるかどうかはチェックしなくてよろしい。 プロトタイプ宣言もつけ加えること。 （最初は i と j とは等しくないと仮定して書いてみて， 書けたものが i と j が等しいときも正しく動くかどうか考えよ。）

(5.3.3) 次はダメな例である。 

    a[i] = a[j];
    a[j] = a[i];

(5.3.4) この関数を呼び出してみなければ，正しく書けたかどうかはわからない。 それには，main() の最後に次のように付け加えればよいだろう。 

    swap(3, 8);
    print();

これで a[3] と a[8] が入れかわっていれば OK である。 swap(8, 3) や swap(3, 3) も試すこと。

(5.3.5) ※ swap(-1, 8) や swap(3, N+1) を実行させるプログラムは， 配列の添え字が範囲外になるので誤ったプログラムである。 そのことを理解したうえで，そういうプログラムを書いて実行してみよ。 ここのコンピュータでは，エラーメッセージなどは出ない。 前者では a[8] に，後者では a[3] に， 配列の“外”にあった値がはいってくることになるが， それは 0 であることが多い。確かめよ。

(5.3.6) ※ プログラムを書く際，間違って swap(-1, 8) や swap(3, N+1) を実行するようなプログラムを書いてしまうことはよくある。 配列を初期化する際，値の範囲を 1 から 99 までとしておいたのは， print() が 0 を出力したら間違いだとすぐにわかるためであった。 a[0] に 0 を代入しておいたのも同様の理由からである。

§5.4 素朴なソート

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

(5.4.2) ※ 配列の要素には等しい値をもつものがあるかも知れないが， その場合のことには深入りしないので，各自考えること。 また，添え字の範囲のうち，常識でわかるものは断らない。

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

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

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

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

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

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

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

(5.5.6) この授業では，ソートにかかった時間で， アルゴリズムの良し悪しを判断することにしよう。 かかる時間は，比較や交換を行なう回数で決まる。

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

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

  1. ソート開始時点で，a[1] から a[1] まではソートされている。 （これは事実を確認しただけであり， 何らかの操作を行なうわけではない。 「--」はまだ調べていないという印である。）
    48------------
  2. a[1] から a[i-1] まではソートされているとき， a[i] をしかるべき位置に挿入して， a[1] から a[i] までがソートされているようにする。
    0305489213----
    ↓
    0305134892----
    （ここでは i は 5 である。 元の a[3], a[4] はそれぞれ一つずつ右にずらした。）

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

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

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

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

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

0305489213----
↓
0305481392----
↓
0305134892----

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

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

(5.6.7) そして，これを，i が 2 から N まで， i の値を一つずつ大きくしながら行なってゆく。

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

§5.7 課題１

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

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

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

#include ...

main() {
    ...

    for (i = ?; i <= ?; i++) {
        printf("いまから a[%d] を挿入します.\n", i);   /* a[] の値も出力する？ */
        for (j = ?; j ???; j??) {
            ...
            swap(?, ?);
            print();
        }
    }
}

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

配列の大きさは .... です.  …………田中美佐子
乱数の種は .......... です.

ここで，配列の大きさ N を 1000000（百万）にし， 初期化の「a[i] = rand();」を「a[i] = i」に変えて実行しよう。 これはもともとデータがソートされていた場合なので，一瞬で終わる。 よく見かけるミスをしていると，なかなか終わらない。 ミスをしていたら前に戻って考え直せ。

(5.7.5) Linux (Unix) では， 「date; ./a.out; date」のようにセミコロンで区切ってコマンド名を書くと， それらが順に実行される。 これで，./a.out の開始時刻，終了時刻がわかり， 差をとることで，実行にかかった時間がわかる。 N の大きさを 50000, 100000, 200000 とし， それぞれについて，五回の実験を行ない， かかった時間の平均を求めよ。 時刻の差や，時間の平均は，手計算か電卓で求めよ。

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

(5.7.7) その次に，プログラムを載せよ。 その際，Active! mail のメール作成画面の「添付ファイル」 *ではなく* 本文の中にソースファイルを貼りつけること。 そのプログラムは，実験を行なったプログラムそのものでなければならない。 （一部でも変更したときは，コンパイル・実行をやり直すこと。）

(5.7.8) 五回の実験結果をまとめてコピペせよ。 すなわち，プロンプトや 「date; ./a.out; date」を含んだままコピペせよ。 （編集すると間違うおそれがあるため。）

(5.7.9) そのあとに，各回にかかった時間と，平均を書け。 「25, 26, 24, 26, 25 秒で平均は 25.2 秒。」のように。

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

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

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

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

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

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

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

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

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

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

岩瀬順一