章末の問題

1. Selection sort, Insertion sort, Merge sort, Shell sort はどのようなソート法か 調べ, これらおよび buble sort, quick sort について計算時間を 500 個から 4000 個程度のデータについて比較せよ. この計測データをもとに shell sort の計算量 $O(f(n))$ の $f(n)$ を推定 しなさい.

2. ソートのループの中に, print 文を挿入し, 20 個程度のデータ についてソートがどのように進んでいるか, 実際のデータについて解説しなさい.

3. 第 6 章の問題 1 の解を高速に求めるプログラムを 作成しなさい. (単なる quick sort では不十分. 全体をソートする必要がない ことに注意. なお, quick sort の応用だと, 最悪計算量が $O(n^2)$ ($n$ は配列 のサイズ) なってしまうが, $O(n)$ アルゴリズムが存在する. 詳しくは [1] 参照.)

Risa/Asir ドリル ギャラリー : $n \log n$ のグラフと $n^2/3$ のグラフ.