3 Sorting



next up previous
Next: 4 CPO Up: 情報処理の方法と演習 問題 Previous: 2 LISP

3 Sorting

3.1
バブルソートのプログラムをCとSchemeで記述し、比較回数を 実際に実行して求めよ。また、それが理論上の比較回数と一致することも確か めよ。

3.2
アルゴリズムによりn個の元をソートするのに必要な平均比較回数の最低値 はいくらか?
また,log(n!)のオーダーを求めよ.

3.3
平均比較回数がであるようなアルゴリズムを一 つ書き、確かにそうであることを証明せよ。それをCまたはSchemeで記述せよ。 ソートする対象は一つの型に固定してよい。

3.4
3.3を、関数ポインタ、あるいは関数引数を利用して、任意のデータ型に 対して適用できるように書き直せ。その場合、比較回数はどうなるか?

3.5
比較回数がであるようなアルゴリズムを書き、証明せよ。 それをCまたはSchemeで記述せよ。



Takashi SAKURAGAWA
Wed Nov 8 12:44:37 JST 1995