アルゴリズムb 第2回

単純な整列アルゴリズム

選択ソート(p.297)、バブルソート(p.294)、挿入ソート(p.300)の３種類が単純なソート $O(n^2)$ です。選択ソートに関しては、先週のプリントを参照して下さい。

バブルソート

バブルソートのアルゴリズム p.294

        n 個の値  a[0], a[1], ..., a[n-1] を並べ替えるには、
        a[n-1]とa[n-2],  ..., a[2]とa[1], a[1]とa[0]のように隣合うデータ
        a[i]とa[i-1]について順にデータを比較し、順序が逆ならば交換する。
	一番前(a[1]とa[0])まで終わったら、また最初から繰り返す。
        交換が起こらなくなったら終了。

BubbleSort.javaの実行例

$ javac BubbleSort.java   
$ java BubbleSort   
データの個数を入力して下さい  8   
20 6 44 74 3 45 13 87   
3 6 13 20 44 45 74 87 
$ java BubbleSort -d   
データの個数を入力して下さい  8   
20 6 44 74 3 45 13 87   
sorting: 3 20 6 44 74 13 45 87 
sorting: 3 6 20 13 44 74 45 87 
sorting: 3 6 13 20 44 45 74 87 
sorting: 3 6 13 20 44 45 74 87 
3 6 13 20 44 45 74 87 
$ java BubbleSort -d2   
データの個数を入力して下さい  8   
20 6 44 74 3 45 13 87   
i=0,j=7: 20 6 44 74 3 45 13 87 
i=0,j=6: 20 6 44 74 3 13 45 87 
i=0,j=5: 20 6 44 74 3 13 45 87 
i=0,j=4: 20 6 44 3 74 13 45 87 
i=0,j=3: 20 6 3 44 74 13 45 87 
i=0,j=2: 20 3 6 44 74 13 45 87 
i=0,j=1: 3 20 6 44 74 13 45 87 
sorting: 3 20 6 44 74 13 45 87 
i=1,j=7: 3 20 6 44 74 13 45 87 
i=1,j=6: 3 20 6 44 74 13 45 87 
i=1,j=5: 3 20 6 44 13 74 45 87 
i=1,j=4: 3 20 6 13 44 74 45 87 
i=1,j=3: 3 20 6 13 44 74 45 87 
i=1,j=2: 3 6 20 13 44 74 45 87 
sorting: 3 6 20 13 44 74 45 87 
i=2,j=7: 3 6 20 13 44 74 45 87 
i=2,j=6: 3 6 20 13 44 45 74 87 
i=2,j=5: 3 6 20 13 44 45 74 87 
i=2,j=4: 3 6 20 13 44 45 74 87 
i=2,j=3: 3 6 13 20 44 45 74 87 
sorting: 3 6 13 20 44 45 74 87 
i=3,j=7: 3 6 13 20 44 45 74 87 
i=3,j=6: 3 6 13 20 44 45 74 87 
i=3,j=5: 3 6 13 20 44 45 74 87 
i=3,j=4: 3 6 13 20 44 45 74 87 
sorting: 3 6 13 20 44 45 74 87 
3 6 13 20 44 45 74 87

外側のループを１回まわるたびに１個ずつデータは正しい位置にきますので、内側のループを回る回数はだんだん減らしていくことができます。

外側のループは $n-1$ 回繰り返されて、内側のループは平均 $n/2$ 回繰り返されます。

内側のループの繰り返し回数: $(n-1) + (n-2) + ... + 2 + 1$

したがって、全体の計算量は $O(n^2)$ となります。

選択ソートとは、外側のループと内側のループの繰り返し回数は同じです。また、内側のループにおける比較の回数も同じとなります。ただし、選択ソートでは、内側のループでは交換は1回しか行われないので (バブルソートでは比較回数の半分は交換が起きると考えられる)、そこがバブルソートよりも実行時間で有利となります。

バブルソートは安定なソートです。 (選択ソートは安定なソートではありません)。

挿入ソート

挿入ソートのアルゴリズム p.300

        n個の値  a[0], a[1], ..., a[n-1] を並べ替えるには、
        配列の一部分(a[0]〜a[i-1])を整列済みの状態にしておき、
        a[i]をa[0]〜a[i-1]の適切な位置に挿入する。
        iを0からn-1まで上記の操作を繰り返せば終了。

InsertSort.javaの実行例

$ javac InsertSort.java   
$ java InsertSort   
データの個数を入力して下さい  8   
20 6 44 74 3 45 13 87   
3 6 13 20 44 45 74 87 
$ java InsertSort -d   
データの個数を入力して下さい  8   
20 6 44 74 3 45 13 87   
sorting: 6 20 44 74 3 45 13 87 
sorting: 6 20 44 74 3 45 13 87 
sorting: 6 20 44 74 3 45 13 87 
sorting: 3 6 20 44 74 45 13 87 
sorting: 3 6 20 44 45 74 13 87 
sorting: 3 6 13 20 44 45 74 87 
sorting: 3 6 13 20 44 45 74 87 
3 6 13 20 44 45 74 87 
$ java InsertSort -d2   
データの個数を入力して下さい  8   
20 6 44 74 3 45 13 87   
i=1,j=0: 6 20 44 74 3 45 13 87 
sorting: 6 20 44 74 3 45 13 87 
sorting: 6 20 44 74 3 45 13 87 
sorting: 6 20 44 74 3 45 13 87 
i=4,j=3: 6 20 44 3 74 45 13 87 
i=4,j=2: 6 20 3 44 74 45 13 87 
i=4,j=1: 6 3 20 44 74 45 13 87 
i=4,j=0: 3 6 20 44 74 45 13 87 
sorting: 3 6 20 44 74 45 13 87 
i=5,j=4: 3 6 20 44 45 74 13 87 
sorting: 3 6 20 44 45 74 13 87 
i=6,j=5: 3 6 20 44 45 13 74 87 
i=6,j=4: 3 6 20 44 13 45 74 87 
i=6,j=3: 3 6 20 13 44 45 74 87 
i=6,j=2: 3 6 13 20 44 45 74 87 
sorting: 3 6 13 20 44 45 74 87 
sorting: 3 6 13 20 44 45 74 87 
3 6 13 20 44 45 74 87

外側のループは $n-1$ 回実行されます。内側のループが実行される回数は、与えられた配列の並び方によって変わりますが、最大で $n-1$ 回です。したがって、全体で計算量は $O(n^2)$ となります。

挿入ソートは、バブルソートと比べると、内側のループで実際のデータを交換する回数は同じとなりますが、比較の回数は少ないです(後から正しい位置まで移動すると、それで内側のループは繰り返しを止めるので)。

ほとんどの要素が整列されている場合は、内側のループはただちに終了します。したがって、「整列済みの配列の後ろに要素を追加して、その配列全体を再び整列させる」ような「ほとんどの要素が整列された状態で整列を行う」場合は、この挿入ソートが適しています。

挿入ソートは安定なソートです。

アルゴリズムb 演習

作成したプログラムが正しく動作することを確認したら、それぞれの提出先に提出しなさい。

提出した後は、正しく提出されていることを http://ynitta.com/class/algoB/local/handin/ で必ず確認しておいて下さい。

提出〆切は、次回の授業の開始時刻です。

課題2a: アルゴリズムによる挙動の違い

提出ファイル	なし
コメント欄:	実行結果と考察
提出先:	「宿題提出Web:アルゴリズムA：課題2a」 http://ynitta.com/class/algoB/local/handin/up.php?id=kadai2a

http://ynitta.com/class/algoB/sortdata/ の下に、次の入力仕様を満たす3種類のデータが置いてあります。これらのデータを手元にダウンロードして下さい(マウスを右クリックして「リンク先を保存する」を選択しましょう)。

rand400k.txt -- $4\times 10^{5}$ 個のデータがランダムに並んでいる
inc400k.txt -- $4\times 10^{5}$ 個のデータが昇べきの順に並んでいる
dec400k.txt -- $4\times 10^{5}$ 個のデータが降べきの順に並んでいる

(これらの中のデータは最小値が0以上で最大値が 400000 未満　であることが保証されています。)

これらのデータそれぞれについて、 SelectionSort.java, BubbleSort.java, InsertSort.java のそれぞれのプログラムがソートするのに要する時間を計測しなさい。その上で、次の3つの質問に答えなさい。

3つのプログラムのうちで、rand200k.txtを処理する時間が最も短いプログラム名を答えなさい。
3つのプログラムのうちで、「入力データの順番と出力のデータの順番が同じデータ」を処理する時間が最も短いプログラム名を答えなさい。さらに、そのプログラムがそのデータを高速に処理できる理由を考察し、答えなさい。
3つのプログラムのうちで、「入力データの順番と出力のデータの順番が完全に逆順のデータ」を処理する時間が最も短いプログラム名を答えなさい。さらに、そのプログラムがそのデータを高速に処理できる理由を考察し、答えなさい。

実行時間の計測には time コマンドを使うこと。データを画面に表示する時間が、測定時間に与える影響を最小限にするために、 Macの「ターミナル」のコマンドラインで

$ time ( java   クラス名   <ファイル名  >dummy) 
[例] $ time ( java  SelectionSort  < rand400k.txt  > dummy)

のように指定して計測すること。

timeコマンドが返す3種類の数字のうちは

real    0m40.606s  ← この値を採用すること(リアル経過時間)
user    0m0.015s
sys     0m0.047s

の場合は、realとして表示されている値を実行時間として採用すること。 (mは分、sは秒を表すので、上の例では40.606秒ということになる。) または、

26.01s user 0.09s system 100% cpu 25.889 total
                                     ↑この値を採用すること(total経過時間)

の場合は total として表示されている値を実行時間として採用すること。

課題2b: ソートの応用例(1)

提出ファイル	ICPC2007a.java
コメント欄:	Sample Inputに対する実行結果
提出先:	「宿題提出Web:アルゴリズムA：課題2b」 http://ynitta.com/class/algoB/local/handin/up.php?id=kadai2b

2007年度ACM-ICPC日本国内予選問題Aより改題

次の問題を解くプログラム ICPC2007a.java を作成しなさい。もしもソートが必要ならば、今回作成した InsertSortクラスの InsertSort.sort(int[]) メソッドを利用すること。

ICPC 得点集計ソフトウェア

世界道化コンテスト (International Clown and Pierrot Competition; ICPC) は興行界で権威も人気も最高の行事である．

このコンテストの特色のひとつは，採点に当たる審判員の数が多いことで，ときには百人にも上る．審判の数は競技者ごとに異なる．というのは，採点対象の競技者と少しでも関係のある審判は，その競技者の演技の採点から一時的に外れるからである．

基本としては，ひとりの競技者の演技についての審判の点数の平均がその競技者の点数になる．常軌を逸した視点から採点する審判が点数に大きな影響を与えないよう，「最高点側から3人の点」と「最低側から3人の点」は除外する．平均点には端数があるかもしれないが，それは切り捨てて最終的な点数は整数値とする．

この行事をテレビ中継向けにスピードアップするため，ある演技の点数を審判全員の採点から計算するプログラム ICPC2007a.java を書くことを，あなたは頼まれた．

Input

入力はそれぞれが競技者の演技ひとつに対応するいくつかのデータセットからなる．入力のデータセット数は20以下である．

データセットの最初の行はある演技の採点に当たった審判の数 $n ~~$ (ただし、$ 7 \leqq n \leqq 100$ ) である。引き続く $n$ 行には各審判のつけた点数 $s_i~~$ (ただし $ 0 \leqq s \leqq 1000$, $~~1 \leqq i \leqq n$ ) がひとつずつ入っている． $n$ も各 $s_i$ も整数である．入力中にはこれらの数を表すための数字以外の文字はない．審判名は秘匿されている．

入力の終わりは $0$ がひとつ含まれた行で示される．

Output

出力は，入力データセットごとにそのデータセットに対応する演技の点数を十進整数で記した一行である．出力行には他の文字があってはならない．

Sample Input

Sample Output

50
74

課題2c: 応用例(2)

提出ファイル	ICPC2016qa.java
コメント欄:	なし
提出先:	「宿題提出Web:アルゴリズムA：課題2c」 http://ynitta.com/class/algoA/local/handin/up.php?id=kadai2c

次の問題を解くプログラム ICPC2016qa.java を作成しなさい。入力 A1.txt に対する出力が A1ans.txt と同一になることを確認したら、プログラムを提出しなさい。

ICPC2016qa.javaの実行例

$ javac ICPC2016qa.java   
$ java ICPC2016qa < A1.txt > a1out.txt       出力をa1out.txtに入れる
$ diff A1ans.txt a1out.txt                   diffコマンドで異なる行を表示させる
$                                  何も出力されずにプロンプトがでれば一致したとわかる

もしもソートが必要ならば、今回作成した InsertSortクラスの InsertSort.sort(int[]) メソッドを利用すること。

2016年度ACM-ICPC日本国内予選問題Aより改題
(注)この問題はソートを使わなくても $O(n^2)$ で解けますが、ソートを使うと $O(n \log n )$ で解けます。もっとも挿入ソートを使うと $O(n^2)$ になってしまいますが...

被験者の選定

筑波博士は，プログラミング教育の新しい方法を考案した。この方法が有効かどうかを確認するために，対照実験を行うことにした。 2 人の学生を被験者として，一方を従来の方法で教え，もう一方を新しい方法で教える。 2 人の最終的な成績を比べれば，新しい方法が有効かどうか判定できるだろう。

公平な比較を行うためには，成績のなるべく近い 2 人を選ぶことが肝要である。手元には，実験に参加可能な学生各人の成績の一覧表がある。この中から成績の差が最も小さい 2 人を選ぶプログラムを書いてほしい．

Input

入力は複数のデータセットからなる．各データセットは次の形式で表される．

$~~~~ n$
$~~~~ a_1 ~~ a_2 ~~ \cdots ~~ a_n$

データセットは 2 行からなる． 1 行目には学生の人数 $n$ が与えられる． $n$ は整数であり， $2 \leqq n \leqq 1000$ が成り立つ． 2 行目には $n$ 人の学生の成績が与えられる． $a_i ~~$ (ただし $1 \leqq i \leqq n$ ) が $i$ 番目の学生の成績である． $a_i$ の値は整数であり，$0$ 以上 $1,000,000$ 以下である．

入力の終わりは，1 個の $0$ だけからなる行で表される．全データセットの n の合計は $50,000$ を超えない．

Output

各データセットについて，成績の差が最小の 2 人の学生を選び，その差（の絶対値）を 1 行に出力せよ．

Sample Input	Output for the Sample Input
5 10 10 10 10 10 5 1 5 8 9 11 7 11 34 83 47 59 29 70 0	0 1 5