《情報基礎論演習》 第９回
【整列】 その２
前回と同様に学生の成績を処理するプログラムを作成する。
成績データファイルは、前回と同じ"s8_8.dat","s8_200.dat","s8_2400.dat"
を使用する。
これらのファイルからデータを読み込み、課題内容に従って処理しなさい。
------------------------------------------------------------------
▼ Basic 1（宿題となっていたもの）
前回（第８回)の演習の Basic 2 のプログラムのソート関数を、クイックソ
ートに変更しなさい。関数の引数が、データの数ではなく範囲であること
と再帰呼びだしになることに注意しなさい。
標準関数に qsort() というクイックソート関数があるが、これは使用せず、
関数は各自で作成しなさい。
(リポートには、"s8_8.dat" の結果を添付すること)
------------------------------------------------------------------
▼ Basic 2
Basic 1 のプログラムに次の処理を追加しなさい。
整列過程におけるデータの比較回数とデータの入れ換え回数を数え、出力
しなさい。
(リポートには、３つのデータファイルそれぞれについて、データの比較
回数、入れ換え回数の出力のみ添付すること)
尚、前回の単純選択整列の回数と比較し、考察しなさい。
データ数が n の時
単純選択整列の比較回数 (n^2-n)/2
単純選択整列の入れ換え回数 n-1
クイックソートの比較回数 Ｏ(n*log2(n))
クイックソートの入れ換え回数 Ｏ(n*log2(n))
(log2(8)=3 log2(200)=7.644 log2(2400)=11.23)
(詳しくは、情報工学基礎論Ｉの講義資料参照)
------------------------------------------------------------------
▼ Basic 3
Basic 1 のプログラムを変更し、得点が同じ場合には学籍番号順(昇順)に
出力されるようにしなさい。(比較の条件を追加すると簡単)
(リポートには、"s8_8.dat"の実行結果を添付すること)
------------------------------------------------------------------
▼ Basic 4
Basic 1 のプログラムを変更し、クイックソート関数を２分探索をする再帰的
定義のサーチ関数に変え、学籍番号を探索（サーチ）キーとする探索プログ
ラムを作成しなさい。
対象となるファイルは学籍番号順（昇順）に整列されているものとする。
０あるいは負の学籍番号が入力されるまで、探索が繰り返し実行できるよう
にし、探索にあたりサーチ関数が何回呼ばれたかを出力しなさい。
探索する学籍番号を変えてサーチ関数が呼ばれた回数が、最大 log2(n)+1 回
（該当者がいる場合）であることを確認しなさい。
------------------------------------------------------------------
▽ Advanced
Basic 3 のプログラムに、整列の過程を出力させる部分を追加し、動作を
可視化して、整列過程を確認しなさい。ソート関数が呼び出された状態、
入れ換えが行なわれた状態などを出力する。
("s8_8.dat"のみ対象とし、実行例を参考にし、各自で工夫しなさい)
/********** Advanced 実行例 **********/
得点(学籍番号)の形式で出力
% advanced s8_8.dat
ソート前
1 安室_奈美恵 56
2 一色_紗英 82
3 小沢_真珠 56
4 菅野_美穂 56
5 佐藤_藍子 82
6 鈴木_沙理奈 26
7 松_たか子 100
8 山口_リエ 90
範囲 [0〜7] 基準得点 56(4)
56(1) 82(2) 56(3) 56(4) 82(5) 26(6) 100(7) 90(8)
56(1) 82(2) 56(3) 90(8) 82(5) 26(6) 100(7) 56(4) d[3]<->d[7]
56(1) 82(2) 56(3) 90(8) 82(5) 100(7) 26(6) 56(4) d[5]<->d[6]
範囲 [0〜5] 基準得点 56(3)
56(1) 82(2) 56(3) 90(8) 82(5) 100(7)
56(1) 82(2) 100(7) 90(8) 82(5) 56(3) d[2]<->d[5]
範囲 [0〜4] 基準得点 100(7)
56(1) 82(2) 100(7) 90(8) 82(5)
100(7) 82(2) 56(1) 90(8) 82(5) d[0]<->d[2]
範囲 [1〜4] 基準得点 56(1)
82(2) 56(1) 90(8) 82(5)
82(2) 82(5) 90(8) 56(1) d[2]<->d[4]
範囲 [1〜3] 基準得点 82(5)
82(2) 82(5) 90(8)
82(2) 90(8) 82(5) d[2]<->d[3]
範囲 [1〜2] 基準得点 82(2)
82(2) 90(8)
90(8) 82(2) d[1]<->d[2]
範囲 [6〜7] 基準得点 26(6)
26(6) 56(4)
56(4) 26(6) d[6]<->d[7]
ソート後
7 松_たか子 100
8 山口_リエ 90
2 一色_紗英 82
5 佐藤_藍子 82
1 安室_奈美恵 56
3 小沢_真珠 56
4 菅野_美穂 56
6 鈴木_沙理奈 26
%
==================================================================
●Javaによるソートアルゴリズムの比較
Sun Microsystems の JDK(Java Developer's Kit) のデモに単純選択整列
(StraightSelectionSort)を追加したものを下記URLに用意しました。
Internet Explorerで閲覧して各ソートの動作を確認しなさい。
図をクリックするとソートを開始します
http://133.34.220.11/~izumi/efcs/SortDemo/sort.html
注意：Netscape では、Jave のプラグインのインストールが必要となり、
閲覧できません。現在このページをNetscapeで開いている人は、Windows
メニューの start -> 検索 -> インターネットでInternet Explorer を起動し、
閲覧してください。