Skip to content

Latest commit

 

History

History
11 lines (6 loc) · 1.14 KB

File metadata and controls

11 lines (6 loc) · 1.14 KB

練習問題12(宿題)

授業中練習問題12 のクリックソートのプログラムでは、常に配列の中央にある値を枢軸として採用しているため、必ずしも領域の分割が効率的に行われるわけではない。枢軸としては、配列の中央にある値ではなく、配列の格納されている値の中央値に近い値を採用することが望ましい。そこで、練習問題12のプログラムの枢軸の選択方法を以下のように変更する。

(1) 分割すべき配列の要素数が 5 以上であれば、配列の先頭・中央・末尾の位置の 3 つの配列の値を取り出し、その中央の値を持つ要素を枢軸として選択するように変更する

(2) 分割すべき配列の要素数が 5 未満であれば 5 つの配列の要素から乱数を使って等しい確率で 1 つを選び枢軸とするよう変更する。さらに、乱数に関しては、教科書 56 ページの乱数による値の設定と教科書 57 ページの Column 2-4 の乱数生成を参考にする。

提出