演習
コマンド行引数として を与えたとき、 個の整数を格納する領域を動的に確保し、その領 域に 個の乱数を格納してから、それをバブルソートし、正しくソートされていることを確 認するするプログラムを作成せよ。プログラムでは、バブルソートにかかった時間（乱数の生 成にかかった時間やソートされていることを確認するためにかかった時間は含めない）も出力 するようにすること。
種々の 目安として、 に対するバブルソートの実行時間を 求めよ。実行時間は、最適化オプション無しでコンパイルした場合と、最適化オプション付き でコンパイルした場合について求め、レポートでは、 とこれら両者の実行時間の関係が一目 でわかるように記載すること。この結果から、 と実行時間の関係を類推し、この類推が理論 的に正しいと言えるかどうか考察せよ。
【ヒントコメント】
¯ プログラムの中に、
を記載してコンパイルエラーになるとの質問があった。構造体はインクルードファ イル の中で定義されているので、プログラム中に記載すると、重定義のエ ラーになる。プログラム例を見れば、上記のような記述は無い事が分かる。
¯ 最適化コンパイルを行っても実行時間が変わらないというレポートがあるが、最適化オプショ ンに必要な「」（大文字のオー）ではなく、間違って「」（数字のゼロ）を指定したた めと考えられる。演習資料節の脚注に記載されているので、演習資料を良く読んでい れば、このようなミスをしなくてすむ。
¯ この課題で「 」や「」が出るのは、多くの場合、確保した配列の 範囲外の要素にアクセスしていることが原因と考えられる。を 型へのポインタ変数と
し、 のようにメモリを動的に確保した場合、ア
クセス可能なのは〜であり、にアクセスすると、
やになる可能性が高い。バブルソートでは、配列の隣の要素との比較を行 うので、このようなエラーが出た場合は、隣の要素がになってしまっていないかを チェックすること。
¯ バブルソートのアルゴリズムの概略として、演習資料に
½º 先頭から順に¾つずつデータを比較し大きい方のデータが後ろになるようにデータを交換 するという操作をデータの最後まで繰り返す。これにより、最後のデータは、最大のデー タとなる。
¾º 最後のデータを取り除いて、再び上記½ºを行う。これをデータが½個になるまで繰り返す。
と記載しているが、これをプログラムにすると、ヒントに記載しているように二重のループ になる。の部分が内側のループで、の部分が外側のループに対応する。
¯ 上記のの部分で、「最後のデータを取り除いて、再び上記を行う。」と指示しているが、
最後のデータを取り除かずに、の操作を 回繰り返しているプログラムが見受けられた。
この方法でもソーティングは出来るが、無駄な比較を行うことになるので遅くなる。
¯ の目安として、 を指示しているが、この規模のデータ数で の実験結果を記載していないレポートは問題である。
¯ 一つの の値に対する実行時間しか載せていないレポートがあるが、 と実行時間の関係を 類推するためには、複数個の に対して実行時間を求める必要がある。
¯ バブルソートの時間複雑度は最悪の場合も平均の場合も ¾ であるので、ソートに要する 時間が ¾にほぼ比例していれば理論通りの結果が得られていることになる。
¯ ソート前やソート後のデータを出力しているプログラムがあるが、プログラム内でソート出 来ていることをチェックしているので、データの出力は不要である。½
¯ バブルソートは非常に有名なソート法なので、演習資料を見ても良く理解出来なかった人は、
「茨木俊秀 によるアルゴリズムとデータ構造!」などの書籍を参考にして勉強しておく こと。
¯ 参考までに、"#$% &" '#$(() '* 上での実験結果を示 す。関数+*の精度などを考えると、実験結果としては小数点以下桁程度の記載 で十分である。
この結果と大幅に異なる場合は、無駄な計算を行っていたり時間を計る場所を間違えている 可能性があるので、プログラムを見直すこと。
演習資料の方法 の操作を 回繰り返す方法 データ数 ソート時間秒 ソート時間秒
最適化無 最適化有 最適化無 最適化有
, &
& - , ,,
- & &
& , -- &
½デバッグのためにデータを出力するのは構わない。
