|
課題 3
例題 2 と 例題 3 のプログラムを参考に任意個の整数でソーティングが実行できるようにしなさい． ただし，個数も実行時（の最初）に読み込むものとする． なお， メモリの確保に失敗した場合はその旨のエラーメッセージを表示して終了させよ．出席票の裏面に課題の実行結果に関する解答欄があります！
実行例
$ ./a.out [Enter]
6 [Enter]
8 15 7 2 100 11 [Enter]
2 7 8 11 15 100
実行データ
実行には次のデータを使用しなさい：- data3A.txt
- data3B.txt
- data3C.txt （※実行には数秒 〜 10 秒程度かかります）
発展問題（加点の対象とする）
前述の選択ソートでは， 最大値を検出して右端と交換するという手順を繰り返していた．これとは逆に， 最小値を検出して左端と交換するという手順を繰り返しても同じ結果になるのは言うまでもない．
ここで，両方を同時にやっていけば繰り返しの回数は約半分になると考えられる． 実際にプログラムにしてみてください． （※ただし，データ交換の回数は変らないので，実行時間の大幅な短縮は期待できない）
これについては，直接メールで阿萬 <aman@cs.ehime-u.ac.jp> まで提出してください．
発展問題 その 2 （加点の対象とする）
本演習では「選択ソート」というアルゴリズムを紹介したが， 実は選択ソートの実行効率はあまり良くない． アルゴリズムはシンプルであり，小規模のデータ処理には十分であるが， 「大量のデータを何度も処理するような場面」 や 「リアルタイム性が求められる場面」 では使い物にならないこともある． 実用面でいえば，クイックソートというアルゴリズムが平均的に最も速いといわれている． C 言語では qsort という関数を利用することでクイックソートを実行できる．qsort を使って整数のソーティングを行うプログラムを作成してみてください． 詳しくは教科書やオンラインマニュアル「jman qsort」を参考にしてください． ※クイックソートのアルゴリズムについては， 後期の「データ構造とアルゴリズム」で詳しく説明します．