これまで、単純なソーティングアルゴリズムを学修してきた。そこで、実際に、 ソーティングアルゴリズムを実装し、入力データとしてランダムデータ、ソー ト済みデータを使い、プログラムの各行が実行される回数の計測を行う。計測 した結果からアルゴリズムの計算量についての考察を行うことを目的とする。
指定されたソーティングアルゴリズムを実装し、プログラムの各行の実行回数を計測し、計算量について考察せよ。また、使用したソーティングのプログラ ムリストを添付せよ。
学籍番号の下1桁によって、考察するソーティングアルゴリズムを次のように指定する。
5月31日までに、指示された提出先へ提出せよ。
入力データ | 比較の時間計算量 | 交換の時間計算量 |
---|---|---|
昇順 | O(?) | O(?) |
降順 | O(?) | O(?) |
ランダム | O(?) | O(?) |
n2の形をしていない |
横軸の値(100, 500, 1000,,,)が等間隔である |
次の例は、線形探索法による探索プログラム (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行目の'}'を追加するとよい。
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
....