3 Sorting

以下で2つ以上の言語で記述した場合には両者の違いを解説すること。

3.1

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

3.2

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

3.3

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

3.4

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

3.5

比較回数がであるようなアルゴリズムを書き、証明せよ。 それをプログラムとして記述せよ。