情報工学実験2

ソフトウェア実験・簡単なソーティング 2009/11/25(水)


課題名: 簡単なソーティング手法

課題: 選択ソート、挿入ソート、バブルソートのうち、自分に割り当てられた手法を用いて以下の問いに答えよ。

(注1) レポートの「アルゴリズム」の項には「 1, 5, 2, 6, 3, 7 」をソートするときのソートの様子を示して適宜注釈を入れること。

(注2) ソートの並びは降順(大→小)とする。

(注3) データ数をn個としたとき、配列の添字は0からn-1までとする。



(1) 実行すると初めに入力するデータ数を入力し、次にデータ(整数)を入力するとソートを 実行して始めの5個と最後の5個のデータを表示するプログラムを作成せよ。

(2) 以下の5つのデータファイルの先頭行には含まれるデータ数、次の行からはデータがランダムに含まれている。

ファイル名 データ数 バイト数
data1 10000 48K
data2 20000 107K
data3 50000 283K
data4 100000 576K
data5 200000 1.3M


全データを /tmp ディレクトリに保存し、ソーティングを行った時の実行時間を測定して次の表を完成させよ。

ファイル名 データ数 real user sys
data1 10000      
data2 20000      
data3 50000      
data4 100000      
data5 200000      

ここで実行ファイル名をfilenameとし、data1をソートする場合は次のように実行する。 この「 < 」を「リダイレクト」と言い、ファイルの中身をキーボードで打つのと同じ動作になる。

$ time ./filename < /tmp/data1

(3) データ数による実行時間の変化を、表計算ソフトを用いて両対数グラフ(横軸:データ数、縦軸:user時間)に描け。