第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)
比較回数 **********回、移動回数 **********回