演習4 演習4プログラムテンプレートテンプレートの説明構造体 struct

演習～単純なソーティングアルゴリズム～
バブルソート，選択ソート，
挿入ソートの実行時間比較
演習４プログラムテンプレート

データの入出力部分はテンプレートを用意したので，こ
れを利用して良い．

このプログラムは，実行時に，コマンドライン引数として
データが格納されたファイル名を必要とする．n = 1000,
10000, 100000の場合のデータファイルを用意している
ので，これを利用して良い．
–
–
–
–
演習4プログラムテンプレート
n=1000の場合のデータファイル
n=10000の場合のデータファイル
n=100000の場合のデータファイル
演習４

データのソーティングを行うプログラムを作成し，データ
数を変化させながら，その実行時間を計測せよ．

この時，単純なソーティングアルゴリズムと呼ばれるバブ
ルソート，選択ソート，挿入ソートの各々のプログラムを
作成・実行し，比較せよ．

データ数を増加させた時の実行時間の増加率を確認し，
理論上の増加率（オーダ）と比較せよ．
テンプレートの説明




大域変数 struct myData data[MAX_N]には整列対象
のデータが格納される．
関数int read_table(char filename[])は引数で指定され
たファイルからキーとデータ値を読み込み，data[]に格納
する．戻り値はデータ数である．
関数void sort(int n)はキーによる整列を行う（各自で作
成する）．第1引数はデータ数nである．
関数void print_data(int n)は整列結果を画面に表示す
る．第1引数はデータ数nである．
構造体 struct myData
演習５（拡張課題）
struct myData {
int key; /* キーとなる整数値 */
char *val; /* データ値の文字列 */
};

このプログラムはシェルソートと呼ばれるアルゴリズムを
実現したものである．実行時間を計測し，結果について
考察せよ． void sort(int n){
int h, i, j;
struct myData d;
for(h = 1; h < n/9; h = h*3+1) ;
for(; h > 0; h /= 3){
for(i = h; i < n; i++){
j = i;
while(j >= h && data[j].key < data[j-h].key){
d = data[j]; data[j] = data[j-h]; data[j-h] = d;
j -= h;
}
}
}
a番目とb番目のデータの交換
struct myData d;
d = data[a]; data[a] = data[b]; data[b] = d;
ISO準拠のC言語処理系の場合，同一型の構造体の代入ではすべて
のメンバ変数が一括代入される．以下と同じこと．
d.key = data[a].key; data[a].key = data[b].key; data[b].key = d.key;
d.val = data[a].val; data[a].val = data[b].val; data[b].val = d.val;
}
1
演習結果報告

演習４（余力があれば５も）を行った結果をまとめ，その
結果が得られた理由についての考察を添えてA4レポー
トを作成せよ．
2

Download Report