2008 年度「計算機基礎論3B」 2008-12-05

§39 素朴なソートの例(その3) --- 挿入ソート

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

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

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

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

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

(39.5) 上の例ではこうなる。
0305489213----
0305481392----
0305134892----
次に 0513 とを比較するが、 ここは逆転していないので、これで操作は終わりである。 その先の比較はする必要がない。

(39.6) プログラムでは、 「j > 1 かつ a[j-1] > a[j] である限り」 と考え、for ループを使うとよいだろう。 「かつ」はC言語では && と書くのだった。

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

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

§40 課題2

(40.1) 前からの準備を元にして、 乱数列で初期化された配列を挿入ソートでソートするプログラムを書け。 また、配列の大きさと比較回数・交換回数との関係を調べよ。 そして、メールでレポートせよ。

  1. まずは、配列の大きさを 8 から 10 程度とし、 プログラムを完成する。 このときは swap() を呼ぶごとに print() を呼び、配列全体を画面に出力させてみるとよい。 途中で「いまから a[5] を挿入します.」のようなメッセージを出すのは、 出力結果に区切りを入れて見やすくするためである。
    #include ...
    
    main() {
        ...
    
        for (i = ?; i <= ?; i++) {
            printf("いまから a[%d] を挿入します.\n", i);
            for (j = ?; j ???; j??) {
                ...
                swap(?, ?);
                print();
            }
        }
    }
    
  2. 次に、配列の大きさを配列全体が画面の一行に収まる範囲でなるべく大きくし、 その場合も正しくソートされることを確かめる。 このとき、print() を呼ぶ回数を減らし、 各 a[i] の挿入が完了した時点でのみ呼ぶ、とするのもよいかもしれない。 (その際、前に書いた print() の呼び出しは消すのではなく、 コメントにして残しておくとよい。)
  3. ここまでできたら、print() の呼び出しはすべて「/*」と 「*/」で囲んでコメントにし、配列の出力はいっさい行なわないようにする。 「いまから ... を挿入します.」の出力も同様にコメントとする。 また、乱数で初期化する関数 init() の中に二つあった 「a[i] = ...;」は「a[i] = rand();」のほうを選ぶ。 これは、同じ値で初期化される要素がなるべく出ないようにするためである。 それから、次のように書き足して、比較回数、交換回数を調べる。 関数 swap() が呼び出されるたびに変数 scount の値が増されるので、 これで swap() が呼び出された回数がわかる。 変数 ccount についても同様。 (配列の大きさ N をいくつに選ぶかは、下を参照。)
    #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];
    }
    
    (このときの出力は
    配列の大きさは .... です.
    乱数の種は .......... です.
    ...... 回比較しました.
    ...... 回交換しました.
    
    のみとなる。)

(40.2) ※ コメント「配列の大きさを出力」 をつけた行を main() の冒頭に入れておくと、 出力結果を見るだけで配列の大きさがわかり、便利である。

(40.3) レポートには、まず、完成したプログラムを載せること。 その際、Active! mail のメール作成画面の「添付ファイル」 *ではなく* 本文の中にソースファイルを貼りつけること。 また、プログラムはそのままコンパイルできる状態のものでなければならない。 (たとえば

#define N       /* ここに配列の大きさを入れてコンパイルしてください */
と書いて送られるとこのままではコンパイルできず、 採点に時間がかかるからやめるように、という意味である。

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

[z08ei0??@ipe???? ~]$ ./a.out
配列の大きさは ????? です.
乱数の種は ?????????? です.
???????? 回比較しました.
???????? 回交換しました.
[z08ei0??@ipe???? ~]$ ./a.out
配列の大きさは ????? です.
乱数の種は ?????????? です.
???????? 回比較しました.
???????? 回交換しました.
    ....
[z08ei0??@ipe???? ~]$ ./a.out
配列の大きさは ????? です.
乱数の種は ?????????? です.
???????? 回比較しました.
???????? 回交換しました.
[z08ec0??@ipe???? ~]$
のようになるだろう。全部をまとめてコピー&ペーストして構わない。 すなわち、プロンプトや「./a.out」がレポートにはいっていてもよい。

(40.5) N の値は三通りに変えるが、 提出するプログラムはそのうちの一つでよい。 ただし、実験を行なったプログラムそのものでなければならない。

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

(40.7) 宛て先は私(岩瀬)の実習用アカウント((25.8) 参照)です。 件名は「kadai2」(←全て半角文字、アルファベットは小文字、 途中にスペースをいれない)としてください。 自分の学籍番号、氏名(として大学に届けてあるもの) をメール本文冒頭に書くのを忘れずに。 締め切りは、諸君の進みぐあいを見たうえで決め、 この実習の最初のページに発表します。

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

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

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

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

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

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

(42.3) 独立した関数にしてもよいし、 main() の最後に置いてもよいだろう。

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


岩瀬順一