プログラミング演習１（課題２：整列：レポート）

レポート課題：整列アルゴリズムの比較

注意事項 課題２－２以降では、ソースコードのmain関数の冒頭にて乱数シードを設定すること。すなわち、以下の記述を含める事。 
    /* 乱数シードを設定(自分の学籍番号の数字　例：222990の場合) */
    srand(222990);
    /* 0からRAND_MAXの一様乱数をn個生成し、配列aに格納 */
    for (i = 0; i < n; i++) {
    a[i] = rand(); 
    }
　　（以下略）
課題２－１）　クイックソートのアルゴリズムのフローチャートを示し、説明せよ。
注意：「フローチャートの書き方」を良く読んだうえで作成する事。再帰呼び出しはサブルーチン呼出しとして記述すること。また、ループの開始・終了の記号は使わず、条件分岐の記号（ひし形）を用いて記述する事。
課題２－２）　降順(大から小)に整列するためのクイックソートのソースコード（正常に動作するコードとコメントつき）を示して解説し、更にN=10の時の実行結果の画面写真を示せ。
課題２－３）　4種（バブルソート・選択ソート・挿入ソート・クイックソート）の整列アルゴリズムを用いて、rand()関数を用いて生成したn個の擬似整数一様乱数(0からRAND_MAX)を整列したときの時間計算量（アルゴリズムの実行にかかった時間）を測定し下記の表を完成し、考察せよ。
整列アルゴリズムの時間計算量比較（単位：秒）
整列対象数(n)バブルソート選択ソート挿入ソートクイックソート
100



1,000



10,000



100,000



オプション課題

オプション課題２－４）　バブルソート、選択ソート、挿入ソートの要素の比較と交換の回数を測定し、下記の表を完成し、考察せよ。
整列アルゴリズムの時間計算量比較（比較回数/交換回数）
整列対象数(n)バブルソート選択ソート挿入ソート
1004,950///
1,000499,500///
10,000///
100,000///
オプション課題２－５）　上記の4種以外の整列アルゴリズムを調べて説明せよ（フローチャート、ソースコードも付加すると良い）。
オプション課題２－６）　クイックソートを再帰呼び出し無しで実装することは可能か検討せよ。また、その際のメリット・デメリットは何か論ぜよ。