|
準備 ファイル data1.dat, data2.dat, data3.dat, data4.dat, data5.dat, data6.dat, data7.dat にそれぞれ系列の異なる 100,000個の整数データ（範囲 1～50000）が格納されている．今回はこれらのファイルをソートデータの対象とする． data1～3 はランダムデータ，data4 は昇順データ，data5 は降順データ，data6 はバイトニックデータ，data7 はジグザグデータである． 課題1 各ファイルに対して，バケットソートを適用してデータをソートさせるプログラム"bucket.c"を実現せよ． 各ファイルに対して，この処理に要する計算時間を測定し，計算量を考察せよ． 課題2 各ファイルに対して，挿入ソートを適用してデータをソートさせるプログラム"insert.c"を実現せよ． 同様に処理時間の測定と計算量の考察を行え． 課題3 各ファイルに対して，バブルソートを適用してデータをソートさせるプログラム"bubble.c"を実現せよ． 同様に処理時間の測定と計算量の考察を行え． 課題4 各ファイルに対して，バブルソートの改良型であるシェーカーソートを適用してデータをソートさせるプログラム"shaker.c"を実現せよ． 同様に処理時間の測定と計算量の考察を行え． 課題5 各ファイルに対して，クイックソートを適用してデータをソートさせるプログラム"quick.c"を実現せよ． 同様に処理時間の測定と計算量の考察を行え． 計算時間が大きくならないように，ピボットの選び方を工夫してみよ． 課題6 これらの結果から各ソート方法にはどのような特徴がわかるか考察せよ． また，上記のソート法の他にどのような方法があるか調べてみよ． 余力のある学生は上記の各ソートにおいて，降順ソートバージョンも実現せよ． 参考 自宅のWindowsにCコンパイラを導入するならMingw-w64をお勧めする． インストールや使い方は多くのページで紹介されている． 
 Copyright (C) 2000 J.LEE Co.,LTD All rights reserved. |