[目的] ソートプログラムの実行時間を測定しオーダーの違いを実感する。 また、データ構造を用いることの利点を理解する。
1. バブルソートのプログラムを作成せよ。
2. ランダムな並びのデータ、ソート済のデータ、逆順にソートされたデータ に対して、バブルソートのプログラムを実行し、実行速度を比較せよ。
3. ヒープソートのプログラムを作成せよ。
4. 2と同様のデータに対して、ヒープソートのプログラムを実行し、実行速度を 比較せよ。
5. 要素数の異なるいくつかのデータに対して、バブルソートのプログラムと ヒープソートのプログラムの実行速度を測定し、実測値と理論値（計算量）を 比較せよ。
6. 1〜5までの結果に基づき、バブルソートとヒープソートの優劣について論ぜよ。
{補足}
・ 入力データのサイズは、たとえばn=1000〜500000など。
使用する計算機によって異なる値を用いる必要があるだろう。
それぞれのアルゴリズムの計算量の理論値との比較ができるような適切な大きさを
選ぶこと。
・ 1と3のプログラムは、ソート本体の関数のみをレポートに示せばよい。
データの入出力は、末尾に添付するプログラム等を参考にせよ。
・ 計測時間にはデータの入出力の時間を含めないように工夫せよ。
実行時間を計測するには、いくつかの方法がある。たとえば、
コマンド (Unix): コマンドの実行時間を計る
コマンド (Unix): 現在の時刻を出力する
Clock (time.h): プログラムの実行に要した経過時間を返す
（どんな単位で経過時間を出力するのかは、計算機によって異なる。
使用する計算機のマニュアル(man clock)を参照のこと。）
時間計測の一つの方法を末尾に添付するプログラムに示す。
レポートに、どのような方法で実行時間を計測したのか明確に書くこと。また、その精度（信頼性）についてコメントすること。
・ 2と4は、実測結果を表にして示すこと。
・ 5は、実測結果を表に示すと同時に、両者の実行時間の振舞いの違いが一目でわかるようなグラフを作成すること。
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define ARRAY_SIZE 1000000
void gen_data(int n, int a[]) /* n個の整数をランダムに生成し、配列aに格納する */
{
int i;
for (i = 0; i < n; i++) {
a[i] = rand();
}
}
void print_result(int n, int a[]) /* ソート結果を出力する */
{
int
i;
for (i
= 0; i < n; i++) {
printf("%d\n",a[i]);
}
}
void insert_sort_sub(int x, int n, int
a[]) /* 挿入法の本体: xを適切な場所に挿入する */
{
int i;
for (i = n
; i >= 0 ; i--) {
if (a[i] <= x) break;
else a[i+1] = a[i];
}
a[i+1] = x;
}
void insert_sort(int n, int a[]) /* 挿入法 */
{
int i;
for (i = 1
; i < n ; i++) {
insert_sort_sub(a[i], i-1, a);
}
}
int main(int argn,
char *argv[])
{
int
a[ARRAY_SIZE];
int n;
clock_t
c1, c2;
if (sscanf(argv[1], "%d", &n) != 1) { /* 第一引数が n */
exit(1);
}
gen_data(n,
a);
c1 = clock();
insert_sort(n,
a);
c2 = clock();
print_result(n,
a);
printf("%d\n",
c2-c1);
}