[ 高橋のページ ]
[ プログラミングおよび実習II ]
プログラミングおよび実習II レポート課題†
以下の要領で，四つのソート法(単純選択法，バブルソート，ヒープソート，クイックソート）のプログラムの実行時間を計測し，これらの性能を比較しましょう．
プログラム作成に関すること†
- 全て，降順にならべかえるようにしてください
- 実験のための乱数データ生成プログラムについては，課題1124-Aのものを使いましょう
- 単純選択法，バブルソートのプログラムについては，課題1201-Aのものをちょこっと修正するだけでよいでしょう
- 四つのソート法のいずれも，工夫してない一番最初のバージョンにしておいて下さい（例えばバブルソートやったら，BubbleSort2()ではなくBubbleSort()の方で実験する）
- ヒープソート，クイックソートのプログラムも，上記と同様に分割コンパイルできるようにして，交換回数をカウントできるようにしましょう
- プログラムのファイル名は，以下の通りにしてください（同じにしておかないと，後で提出してもらう際に受け付けられないかもしれません） main() を含むプログラムのファイル名は，好きにつけてもらって構いません
- printdata2.c
- 関数 PrintData2() を含む
- selection.c
- 関数 SelectionSort() を含む
- bubble.c
- 関数 BubbleSort() を含む
- heap.c
- 関数 HeapSort() 他を含む
- quick.c
- 関数 QuickSort() 他を含む
- 上記の関数たちの引数の型や順番なども，実習課題として指定されたものに合わせておいてください（同じにしておかないと，後で提出してもらう際に受け付けられないかもしれません）
実験に関すること†
実験その一： 交換回数の計測†
四つのソート法のプログラムに対して，種を「学籍番号の下5桁（TXYabcdな人は，Yabcd，T00abcdな人は，8abcd）」にして発生させた乱数データ1000個を入力し，それぞれの交換回数を求めてください．
実験その二： 実行時間の計測†
データの個数をいろいろ変えながら四つのソート法のプログラムをそれぞれ何回か実行し，以下のようにして実行時間を計測してください．
例えば，乱数データの生成用プログラムの実行形式がrandom，バブルソートのプログラムの実行形式がbubbleだった場合，
$ ./random | (time ./bubble )
と実行して，種とデータ個数を入力すれば，bubbleの出力の後に
real 0m2.462s ← 実際の経過時間 0分2.462秒
user 0m0.603s ← そのうち，このプログラムの実行に使った時間
sys 0m0.002s ← このプログラムの実行のためにOSなどが使った時間
というような出力がされます．このレポート課題では，「"user"の時間 = ソートプログラムの実行に要した時間」と考えて，この値を記録していってもらえれば結構です．
以下のことに気をつけましょう
- データ個数があまり少ないと，実行時間も小さすぎて有効な時間計測ができないかもしれません
- 乱数データを使って実験しますから，同じ実験条件（あるソート法，あるデータ個数）でも種を変えると結果が変わります．また，timeコマンドで計測される実行時間には結構誤差があります．同じ実験条件でも種を変えて何度か実験し，得られた実行時間の平均を実験データとしましょう．
- 当然のことですが，実験に使う計算機の性能が異なれば実行時間も異なる結果となります．一連の実験は同じ性能の計算機上でやらないと意味がありません．ですが，1-542, 1-609, 3号館セルフラーニング室などの計算機は全て同じ性能ですので，どこでやっても大丈夫です（注：1-612のものは同じではありません）．Linuxの場合，次のようにすればCPUのクロック周波数やキャッシュメモリのサイズなどを知ることができます．
$ cat /proc/cpuinfo
実験その三： 自由研究（ボーナス課題）†
余裕があったら自分なりにいろいろ研究してみてください．レポートの点数にボーナス点を追加することがあります．
例えば，アルゴリズムやプログラムに工夫を加えたものでも実験して比較する，実験データを変えてみる，などなど．
アイデアをいくつかあげてみると…
- 昇順や降順にソート済みのデータなどでも実験してみる（特に，クイックソートの基準値を先頭または末尾の要素からとるようにしてみると面白いでせう）
- 両対数目盛でグラフを描いて考察してみる
- 自宅のPCでも実験して，実習室のと比較してみる
- コンパイラの最適化オプションを指定してみる($ man cc して，「最適化オプション」を探してみる)
- その他お好きにどうぞ
考察やレポート作成に関すること†
グラフ†
横軸にデータ個数，縦軸に実行時間をとって，グラフを描きましょう．四つのソート法を比較したいので，全部ひとつのグラフに描きたいところですが，あまりに値が違いすぎて困るかもしれません（両対数目盛なら全部一緒にかけますが…）．せめて，単純選択法とバブル，ヒープとクイックのそれぞれのペアについて一緒にグラフを描きましょう．
グラフを描く際は，以下のどれでもよいです．
- gnuplotを使う (gnuplotの使い方)
- その他自分の好きなソフトを使う
- 方眼紙に手書き（ただしきれいに描いてね）
どのソート法が速いのか，データ個数と実行時間の間にはどんな関係があるのか，それはなぜか，など
レポートに書くべきこと†
数字やグラフなどの結果を羅列しただけのものは受け取りません．きちんと文章で記述してください．
- 実験条件（データ個数をいくつとして実験したか，など）
- 実験結果
- 数値（例えばバブルソートでデータ個数1000個のとき実行時間の平均はいくつ，など）
- グラフ
- 考察
- その他何か書きたいことがあればご自由にどうぞ
提出に関すること†
- 提出法
- レポート: 適当なA4用紙にまとめて適当に綴じた（左上綴じやとうれしいです）ものを，高橋に手渡すか箱に入れる
- プログラム: レポート締め切りまでに，「menuコマンド」を使って，selection.c, bubble.c, heap.c, quick.c を提出してください．これらを提出しないと，レポートは採点しません． 締め切り前ならば，menuコマンドによる提出は何回でもできます．複数回提出した場合，新しい方のみが高橋の手元に残るようになっています．
- 締め切り
- 12月22日18時30分
- 1-508の扉に提出用の箱が置いてあります
![[PukiWiki]](image/blackuni3-80x80.png "[PukiWiki]")
