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

§29 素朴なソート

(29.1) しばらくの間、プログラミングを離れて、 ソートの「アルゴリズム」について考えてみよう。 「アルゴリズム」とは、 問題を解くための手順をあいまいさのないように書いたもののことである。

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

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

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

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

(30.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) である。 N2/4 = Ο(N2) でもあるが、 N(N-1)/2 = Ο(N2) = N2/4 から N(N-1)/2 = N2/4, などと考えてはいけない。

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

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

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

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

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

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

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

次に

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

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

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

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

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

(32.2)

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

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

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

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

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

§33 素朴なソートの例（その３） --- 挿入ソート

(33.1) 挿入ソートは、次に学ぶ Shell ソートの基礎になる。 次の二つを利用して配列をソートするものである。

  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] はそれぞれ一つずつ右にずらした。）

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

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

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

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

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

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

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

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

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

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

§34 課題１

(34.1) 前からの準備を元にして、 乱数列で初期化された配列を挿入ソートでソートするプログラムを書け。 また、配列の大きさと比較回数・交換回数との関係を調べよ。 そして、メールでレポートせよ。 ファイル名は insert.c がよいかも知れない。 （英語では insertion sort と呼ばれるが。）

  1. 元にするのは、前回分で swap() と comp() を付け加えたソースファイルである。 これらの関数のテスト用として main() に書き加えた部分は削除する。 まずは、配列の大きさを 8 から 10 程度とし、 プログラムを完成する。 このときは swap() を呼ぶごとに print() を呼び、配列全体を画面に出力させる。 途中で「いまから a[5] を挿入します.」のようなメッセージを出すのは、 出力結果に区切りを入れて見やすくするためである。 
    #include ...

main() {
    ...

    for (i = ?; i <= ?; i++) {
        printf("いまから a[%d] を挿入します.\n", i);
        for (j = ?; j ???; j??) {
            ...
            swap(?, ?);
            print();
        }
    }
}
  2. 次に、配列の大きさを 20 にする。 それから、次のように書き足して、比較回数、交換回数を調べる。 
    #include ...

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

main() {
    int i, j;

    printf("配列の大きさは %d です.\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 についても同様。 これで、比較回数・交換回数が (33.8) に書いた値に近いことを確認する。 （違っていたら、前に戻ってやり直し。）
  3. ここまでできたら、print() の呼び出しを「/*」と 「*/」で囲んでコメントにし、配列の出力はいっさい行なわないようにする。 「いまから ... を挿入します.」の出力も同様にコメントとする。 また、乱数で初期化する関数 init() の中に二つあった 「a[i] = ...;」は「a[i] = rand();」のほうを選ぶ。 これは、同じ値で初期化される要素がなるべく出ないようにするためであった。 配列の大きさ N をいくつに選ぶかは、下を参照。 このときの出力は次のようになる。 
    配列の大きさは .... です.
乱数の種は .......... です.
...... 回比較しました.
...... 回交換しました.

(34.2) メールの本文冒頭に、 学籍番号、名列番号、氏名（として大学に届けてあるもの）を忘れずに書け。 次に、レポートの内容を、「挿入ソートのプログラムと実験結果」程度に、 簡潔に書け。

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

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

[z11ec???@ipe???? ~]$ ./a.out
配列の大きさは ????? です.
乱数の種は ?????????? です.
???????? 回比較しました.
???????? 回交換しました.
[z11ec???@ipe???? ~]$ ./a.out
    ....
[z11ec???@ipe???? ~]$ ./a.out
配列の大きさは ????? です.
乱数の種は ?????????? です.
???????? 回比較しました.
???????? 回交換しました.
[z11ec???@ipe???? ~]$

これらすべて（最低でも１５回分）を、 全部をまとめてコピー&ペーストして送れ。 すなわち、プロンプトや「./a.out」がはいったまま送れ。

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

(34.6) 宛て先は私（岩瀬）の実習用アカウント（(11.9) 参照）である。 件名は「kadai1」（←全て半角文字、アルファベットは小文字、 途中にスペースをいれない）とせよ。

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

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

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

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

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

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

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

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

付）double 型の誤差についての実験

小数点未満がある数を扱う double 型では、 誤差に注意が必要である。 次のプログラムは、0.1 の整数倍をテストしている。 

#include <stdio.h>

main() {
    int n;
    double x;

    printf("0.1 と入力してください.\n");
    scanf("%lf", &x); printf("x の値は %f です.\n", x);     /* 一行に書いたのは行数の都合 */
    for (n = 0; n <= 10; n++) {
        printf("x の %d 倍は %.60f です.\n", n, n*x);   /* %.60f は小数点以下 60 けたの意 */
    }
    if (10*x == 1.0) {
        printf("x の 10 倍と 1.0 とは等しい.\n");
    } else {
        printf("x の 10 倍と 1.0 とは等しくない.\n");
        printf("   その差は %.60f です.\n", 10*x - 1.0);
    }
}
岩瀬順一