データ構造とアルゴリズムⅡ (2024年度) レポート課題
ソーティングの計算量に関する考察
▼目的
単純なソーティングアルゴリズムに続いて、シェルソート、クィックソート、 マージソート、ヒープソートを学修してきた。そこで、実際に、これらのソーティングアルゴリズムを実装し、入力データとしてランダムデータ、ソート済みデータを使い、 プログラム中の比較操作・交換操作に相当する行の実行回数を計測する。計測した結果からアルゴリズムの計算量についての考察を行うことを目的とする。 ただし、実装するソーティングアルゴリズムは、昇順にソートするものとする。
▼課題
指定されたソーティングアルゴリズムを実装し、プログラムの各行の実行回数を計測し、計算量について考察せよ。また、使用したソーティングのプログラ ムリストを添付せよ。
学籍番号の下1桁によって、考察するソーティングアルゴリズムを次のように指定する。
- 下1桁が3, 7の人 ： シェルソート
- 下1桁が4, 8の人 ： クイックソート
- 下1桁が1, 5, 9の人 ： マージソート
- 下1桁が2, 6, 0の人 ： ヒープソート
▼提出締切と提出先
6月30日までに、指示された提出先へ提出せよ。
▼条件
- 添付のファイルをレポートのフォーマットです。また、表紙の全てのチェック項目をチェックして、全てが○であること。表紙のダウンロード(Word)
- データが昇順にソートされている場合、降順にソートされている場合、 および、ランダムな場合の3種類について、プログラムの各実行文の実行回数を計測せよ。ただし、整列アルゴリズムは、降順に整列するように実装すること。
- 入力データ数は、100、200、300、400、500とか、1000、2000、3000、4000、5000 とかを使用し、計算量の議論やグラフ作成上の都合に応じて、これら以外の値も積極的に使用せよ。
- 時間計算量は、入力データが昇順・降順・ランダムの３つの場合のそれぞれについて、交換操作と比較操作に分けて述べること。結論は、次のような表にまとめること。
入力データ 比較の時間計算量 交換の時間計算量 昇順 O(?) O(?) 降順 O(?) O(?) ランダム O(?) O(?)
- なお、計算量を上記3の表にまとめる前に、計測した「実行文の実行回数」をもとに、入力データ数によって比較操作と交換操作の実行回数がそれぞれどう変化しているかに着目して、そのように結論づける理由を述べよ。教科書p.192のTable12.1, 12.2なども議論の参考にして良い。
重要なことは、入力データ数が 2倍になったとき、実行回数が 2 倍になるのか、それとも4倍になるのか。入力データ量が3倍になればどうなるのか、それはなぜなのかを考えることである。
単に「グラフを見ると y = x2の形をしているので、O(n2)である。」といった乱暴な結論ではダメ。なぜなら、そのグラフは O(n3) や O(n1.5) かもしれない。
また、「内側のループが何回まわって、外側のループが何回まわるから…」といったプログラムの動作説明は教科書に書かれているので、その詳細をレポートに書き写すことは不要である(これらを理解していることは、当然の前提である)。 - 議論の参考のために、gnuplot, Excel などのグラフ描画機能を利用し、グラフを作成せよ。
- 手書きは不可とする。
- 次のような、O(n2)の議論に使えない不適切なグラフを描いたレポートは再提出を求める。
n2の形をしていない
横軸の値(100, 500, 1000,,,)が等間隔である
また、グラフの軸の名前がない場合、軸の数値がおかしい場合も原則差し戻すので、注意すること。
参考
gnuplot とは、unix上でグラフを作成するツールである。 2次元ならば xy座標をファイルに入れておいて(プログラムで作成して おいて)、それを読ませることで、グラフが作成される。 使い方は、下記のページを参照せよ。サンプルコード
サンプルは線形探索を行うアルゴリズムを記載している。また、サンプルコードはC言語とPythonで用意している。使用しやすい言語を利用すること。
また、GitHubにも同様のコードがある.