データ構造とアルゴリズム

Front

実験の説明 †

実習は５週行う。

• 少なくとも５種類

  単純選択
  単純挿入
  バブル
  マージ
  クイック

  について実験を行う。
• これらの実験の終わった者は、その改良版や、比較によらない方法

  バケットソート法
  ラディックスソート法
  etc...

  も試してみるように。
• もちろん自分で改良と思えることは試してみると良い。

レポートはA4縦で以下のように作成し、期末試験開始時期までには提出するように。

1. 表紙

   題名：データ構造とアルゴリズム実習レポート
   提出年月日
   学籍番号
   氏名

2. ソースリスト
   実験を行ったプログラムのソースリスト
   
3. グラフ
   すべてのアルゴリズムの計算時間をひとつのグラフにまとめて記載する。
   比較しやすいように。
   
4. 評価
   実験結果がなぜそうなるのかの考察

アルゴリズムの実行時間の計り方 †

プログラムのアルゴリズム部分の処理に要した時間を求めてください．

• 以下に例を示します．

  #include <stdlib.h>
  #include <time.h>
  
  #define MAX 20000/* 要素の最大数 */
  
  int main(void) {
  	int element[MAX+1];
  	clock_t before, after;/* プログラムで使われたプロセッサ時間を返す */
  	int i;
  	int num;/* 要素数の変数 */
  
  	srand(getpid());
  	printf("要素数:");
  	scanf("%d", &num);
  	for(i=1; i<=num; ++i)/* 要素の初期設定 */
  		element[i]=rand();
  
  	before = clock();/* 処理開始時のプロセッサ時刻を取得 */
  
  	/* 
  		ここにアルゴリズムのメインルーチンを置く
  	*/
  
  	after = clock();/* 処理終了時のプロセッサ時刻を取得 */
  
  	printf("%f\n", (float)(after - before)/CLOCKS_PER_SEC);
  	/* （アルゴリズムに要した時間）＝（処理後の時刻）−（処理前の時刻） */
  	/* clock()/CLOCKS_PER_SECは秒で表された時間 */
  
  	/*
  		アルゴリズムの実行確認のためのデータ出力はここに記述する
  	*/
  
  	return 0;
  }

注意 †

マージソート法について

• 教科書のままのプログラムだと要素数が２のべき乗の時しか正常に動作しないので
  要素数を入力するときに２のべき乗を入力してください。