データ構造とアルゴリズムⅡ (2022年度) レポート課題
ソーティングの計算量に関する考察
▼目的
これまで、単純なソーティングアルゴリズムを学修してきた。そこで、実際に、 ソーティングアルゴリズムを実装し、入力データとしてランダムデータ、ソー ト済みデータを使い、プログラムの各行が実行される回数の計測を行う。計測 した結果からアルゴリズムの計算量についての考察を行うことを目的とする。
▼課題
指定されたソーティングアルゴリズムを実装し、プログラムの各行の実行回数を計測し、計算量について考察せよ。また、使用したソーティングのプログラ ムリストを添付せよ。
学籍番号の下1桁によって、考察するソーティングアルゴリズムを次のように指定する。
- 下1桁が3,6,9の人 ： バブルソート
- 下1桁が1,4,7,0の人 ： 選択ソート
- 下1桁が2,5,8の人 ： 挿入ソート
▼提出締切と提出先
5月31日までに、指示された提出先へ提出せよ。
▼条件
- 添付のファイルをレポートのフォーマットです。また、表紙の全てのチェック項目をチェックして、全てが○であること。表紙のダウンロード(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言語）
次の例は、線形探索法による探索プログラム (p.12 List2.1参考)の各行にs[X]++;を挿入して計測した例である。
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAX_ELEMENTS 10000 /* 最大のデータ数 */
#define OFFSET 100 /* データ数の増分値 */
#define MAX_LINES 10 /* 関数の最大行数 */
int a[MAX_ELEMENTS] ; /* 探索するデータ領域 */
int s[MAX_LINES]; /* 各行の実行回数格納領域 */
int search(int, int);
void init_step(void);
void print_step(int);
void print_header(char *);
int sorted(int);
int main(void){
int i;
int n; /* データ数 */
srandom(time(0)); /* 乱数の種を初期設定する */
/* ランダム入力の場合 */
print_header("random");
for (n = OFFSET; n <= MAX_ELEMENTS; n += OFFSET) {
printf("%4d", n);
init_step(); /* 配列sの初期化 */
for (i = 0; i < n ; i++) {
a[i] = random() % n ; /* 配列要素に乱数値を設定する */
}
search(n, n/3); /* 線形探索を実行 */
/* ここに昇順のチェックをいれる */
/* ここまでに昇順のチェックをいれる */
print_step(n); /* 各行の実行回数表示 */
}
/* 昇順にソートされた入力の場合 */
print_header("ascending order");
for (n = OFFSET; n <= MAX_ELEMENTS; n += OFFSET) {
printf("%4d", n);
init_step(); /* 配列sの初期化 */
for (i = 0; i < n ; i++) {
a[i] = i ; /* 配列要素に昇順のデータ値を設定する */
}
search(n, n/3); /* 線形探索を実行 */
if (!sorted(n)) { /* 配列が昇順に整列されているかチェック */
fprintf(stderr, "%d not sorted\n", n);
exit(1);
}
print_step(n); /* 各行の実行回数表示 */
}
/* 降順にソートされた入力の場合 */
print_header("descending order");
for (n = OFFSET; n <= MAX_ELEMENTS; n += OFFSET) {
printf("%4d", n);
init_step(); /* 配列sの初期化 */
for (i = 0; i < n ; i++) {
a[i] = n - i ; /* 配列要素に降順のデータ値を設定する */
}
search(n, n/3); /* 線形探索を実行 */
/* ここに昇順のチェックをいれる */
/* ここまでに昇順のチェックをいれる */
print_step(n); /* 各行の実行回数表示 */
}
return 0;
}
void init_step(){
int i;
for (i=0; i < MAX_LINES ; i++)
s[i] = 0;
}
void print_step(int n){
int i;
for (i = 0; i < MAX_LINES ; i++) {
printf(", %5d", s[i]);
}
printf("\n");
}
void print_header(char *s) {
int i;
printf("%s\n n", s);
for (i = 0; i < MAX_LINES ; i++) {
printf(", line%d", i);
}
printf("\n");
}
int sorted(int n) {
int i;
for (i = 0; i < n - 1; i++) {
if (a[i] > a[i+1]) return 0;
}
return 1;
}
int search(int n, int key){
int i;
s[0]++; i = 0;
s[1]++; while (i < n) {
s[2]++; if (a[i] == key) {
s[3]++; return (key);
s[4]++; }
s[5]++; i++;
s[6]++; }
s[7]++; return -1;
}for,while,if文がブロックになっていない場合には、s[X]++; を挿入することで、アルゴリズムを変えてしまう可能性があるので上記のように 105,106行目の'{',108,110行目の'}'を追加するとよい。
サンプルプログラムの出力
次の例は、サンプルプログラムの出力の一部である。このように,(カンマ)で 区切られたデータを用意することで、表計算ソフトに手でデータを一つずつ入力 （あるいはコピー）する手間を省くことができる。具体的には、次のような操作をすればよい。 プログラムの出力をコピーしてテキストファイルに保存し、そのテキスト ファイルの拡張子を.csv にする。次にそのCSVファイルを Excel で開いて、 行と列を転置 すれば、実行回数の変化のグラフを描きやすい形でデータを まとめることができる。（転置しなくても、メニューからグラフツール→デザイン→データ 選択 で横軸を n の値に設定しなおせばよい。）
n, line0, line1, line2, line3, line4, line5, line6, line7, line8,line9
100, 1, 1, 100, 0, 0, 100, 100, 1, 0, 0
200, 1, 1, 60, 1, 0, 59, 59, 0, 0, 0
300, 1, 1, 292, 1, 0, 291, 291, 0, 0, 0
400, 1, 1, 400, 0, 0, 400, 400, 1, 0, 0
500, 1, 1, 500, 0, 0, 500, 500, 1, 0, 0
600, 1, 1, 600, 0, 0, 600, 600, 1, 0, 0
700, 1, 1, 340, 1, 0, 339, 339, 0, 0, 0
800, 1, 1, 800, 0, 0, 800, 800, 1, 0, 0
900, 1, 1, 900, 0, 0, 900, 900, 1, 0, 0
....