第8回 演習問題 基数整列法

■ 共通
実行・測定環境
 OS: linux
測定時は、当該プログラム以外のプログラムはできるだけ削減する

8a クイックソートと基数交換法の比較
■ 実験用データ
 整数集合:  集合の濃度(要素数): 1,000,000、 キーの型: 整数、   ファイル: integer1MR.dat

 上記のデータから下記の4種類のデータを作成し、2つの整列アルゴリズムを用いて整列する。
 200,000  400,000  600,000  800,000  1,000,000
上記の4つのデータに対して比較回数、移動回数、処理時間を以下のように出力する。計測結果について、理論値、その他様々な観点から分析しなさい。 ◆ 出力例
クイックソート
比較回数 **********回、移動回数 **********回 処理時間*********msec

基数交換法
比較回数 **********回、移動回数 **********回 処理時間*********msec



8b クイックソートと直接基数法の比較
■ 実験用データ
 整数集合:  集合の濃度(要素数): 10,000,000、 キーの型: 整数、   ファイル: integer10MR.dat

 上記のデータから下記の4種類のデータを作成し、2つの整列アルゴリズムを用いて整列する。
 2,000,000  4,000,000  6,000,000  8,000,000  10,000,000
上記の4つのデータに対して比較回数、移動回数、処理時間を以下のように出力する。計測結果について、理論値、その他様々な観点から分析しなさい。 ◆ 出力例
クイックソート
比較回数 **********回、移動回数 **********回 処理時間*********msec

直接基数法
比較回数 **********回、移動回数 **********回 処理時間*********msec



8c 直接基数法の比較
■ 実験用データ
 整数集合:  集合の濃度(要素数): 10,000,000、 キーの型: 整数、   ファイル: integer10MR.dat

 カウンターの大きさを10(基数の1桁)ではなく、100(基数の2桁)にして、前者と後者で比較回数、移動回数、処理時間を比較する。
 2,000,000  4,000,000  6,000,000  8,000,000  10,000,000
上記の4つのデータに対して比較回数、移動回数、処理時間を以下のように出力する。計測結果について、理論値、その他様々な観点から分析しなさい。 ◆ 出力例
直接記数法(カウンターの大きさ: 10)
比較回数 **********回、移動回数 **********回

直接記数法(カウンターの大きさ: 100)
比較回数 **********回、移動回数 **********回