2005 年度「計算数学１」 2005-04-06

出力の行数が多くて一画面に収まりきらない場合は ./a.out の代わりに「./a.out | more」とする。画面左下に「--続ける--」が出たらスペースバーで次の画面、 Enter で次の行、q で中止。

プログラムの実行時間を計るには、「date; ./a.out; date」として開始・終了時刻を表示させ、引き算すればよい。ただし、./a.out の出力が多いと初めの date の出力が消えてしまいうまくゆかない。

素朴なソート

配列は a[0], a[1], ..., a[N-1] とする。全部で N 項である。配列の要素には等しい値をもつものがあるかも知れないが、その場合のことには深入りしないので、各自考えること。添字の範囲のうち、常識でわかるものは断らない。

「a[i] > a[i+1] を満たす i があったら a[i] と a[i+1] とを交換する。これをくり返してゆく」というのがこのソートのアイディアである。

「転倒数」を # {(i, j) | i < j かつ a[i] > a[j]} で定義する。これは Σ_j # {i | i < j かつ a[i] > a[j]} とも思える。次の事実の証明はやさしい。

上のような交換を一度行なうと、転倒数は 1 だけ減少する。
転倒数が 0 であるための必要十分条件は配列が整列されていることである。
配列が整列されていなければ、a[i] > a[i+1] となる i が存在する。

これらから、この操作をくり返してゆけばいつか整列が完了することがわかる。

付）配列に格納されている値が 0, 1, 2, ..., N-1 を並べかえたものであるとき、 a は置換と思える。その符号 (sgn) は転倒数が偶数なら +1, 奇数なら -1 である。よって、置換の符号を転倒数から定義することもできる。なお、このとき、転倒数は a を (i i+1) のタイプの互換の積で書いたときの互換の数の最小に等しい。

a[i] > a[i+1] なる i のさがし方はいろいろ考えられる。その一つ。

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

これで最大の値をもつもの（のうちの一つ）が a[N-1] にはいったことを確かめよ。次に

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

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

このアルゴリズムでの、比較回数（= 比較の回数）はおよそ N²/2 である。交換回数（= 交換を行なった回数）は最悪の場合およそ N²/2, 最も lucky な場合は 0, 平均すると N²/4 とみてよいだろう。どちらもΟ(N²) である。

課題４

課題 4-1) 乱数列で初期化された配列をこの素朴な方法でソートするプログラムを書け。また、配列の大きさと所要時間の関係を調べよ。

まずは、配列の大きさは 10 以下程度とし、プログラムを完成する。このときは swap() を呼ぶごとに配列全体を画面に出力させてみるとよい。
次に、配列の大きさを配列全体が一行に収まる程度まで大きくしてみる。ここで swap() を呼ぶタイミングを変えて、 a[N-1], a[N-2], ... が確定するごとに、とするのもよいかもしれない。
最後に、配列の大きさを 100, 1000, 10000 などと徐々に大きくして、配列の大きさと所要時間との関係を調べる。このときは途中の出力は行なわない。また、乱数で初期化するところの「% 100」を取り去ること。こうしないと同じ値がたくさん出てきてしまうためである。

課題 4-2) 次のように書き足すと、関数 swap() を呼び出した回数がわかる。これを利用し、配列の大きさと交換を行なった回数との関係を調べよ。

#include ...

int count = 0;

int main() {
    ...
    printf("%d 回交換しました.\n", count);
}


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

    count++;
}

付）比較の回数もカウントするなら、上と同様に int 型変数（たとえば）ccount を定義し、 if (a[i] > a[i+1]) を if (ccount++, a[i] > a[i+1]) と変えればよい。このカンマはカンマ演算子である。

以上から適当に選んで、メールでレポートしてください。

プログラムも送ってください。その際、Active!Mail のメール作成画面の「添付ファイル」 *ではなく* 本文の中にソースファイルを貼りつけること。

所要時間を計るにせよ回数を数えるにせよ、数回くり返して測定し、それらのデータそのものおよび平均値をレポートに書くこと。それから、理論上の値などと比較すること。感想は書かなくてもよい。

宛て先は私（岩瀬）の実習用アカウント cf5326@mailedu1.ipc.kanazawa-u.ac.jp です。件名は「kadai4」（←全て半角文字、アルファベットは小文字、途中にスペースをいれない）としてください。自分の学籍番号、氏名（として大学に届けてあるもの）をメールの *本文内にも* 書くのを忘れずに。

補

先学期の「計算機基礎論３Ｂ」の最後に紹介した、最大値を求めて交換してゆくやり方も、素朴なソートの一種である。これは交換回数は（高々）N だが、比較回数はおよそ N²/2 である。これも、興味のある人は上にならっていろいろ実験してみるとよい。

岩瀬順一