バブルソートのアルゴリズム 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の実行例 |
|
外側のループを1回まわるたびに1個ずつデータは正しい位置に きますので、内側のループを回る回数はだんだん減らしていくことができます。
外側のループは $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の実行例 |
|
外側のループは $n-1$ 回実行されます。 内側のループが実行される回数は、与えられた配列の並び方によって変わりますが、最大で $n-1$ 回です。 したがって、全体で計算量は $O(n^2)$ となります。
挿入ソートは、バブルソートと比べると、内側のループで 実際のデータを交換する回数は同じとなりますが、 比較の回数は少ないです(後から正しい位置まで移動すると、 それで内側のループは繰り返しを止めるので)。
ほとんどの要素が整列されている場合は、内側のループはただちに 終了します。したがって、「整列済みの配列の後ろに要素を追加して、 その配列全体を再び整列させる」ような「ほとんどの要素が整列された 状態で整列を行う」場合は、この挿入ソートが適しています。
挿入ソートは安定なソートです。
作成したプログラムが正しく動作することを確認したら、それぞれの 提出先に提出しなさい。
提出した後は、正しく提出されていることを http://ynitta.com/class/algoB/local/handin/ で必ず確認しておいて下さい。
提出〆切は、次回の授業の開始時刻です。
提出ファイル | なし |
---|---|
コメント欄: | 実行結果と考察 |
提出先: | 「宿題提出Web:アルゴリズムA:課題2a」 http://ynitta.com/class/algoB/local/handin/up.php?id=kadai2a |
http://ynitta.com/class/algoB/sortdata/ の下に、次の入力仕様を満たす3種類のデータが置いてあります。 これらのデータを手元にダウンロードして下さい(マウスを右クリックして「リンク先を保存する」を選択しましょう)。
これらのデータそれぞれについて、 SelectionSort.java, BubbleSort.java, InsertSort.java のそれぞれのプログラムがソートするのに要する時間を 計測しなさい。 その上で、次の3つの質問に答えなさい。
実行時間の計測には time
コマンドを使うこと。
測定時間が、データを画面に表示する時間の影響を最小限にするために、
Macの「ターミナル」のコマンドラインで
$ time ( java クラス名 <ファイル名 >dummy) [例] $ time ( java SelectionSort <sdata1.txt >dummy)のように指定して計測すること。
timeコマンドは
real 0m40.606s ←この値を採用すること(リアル経過時間) user 0m0.015s sys 0m0.047sのように3種類の値を表示するが、realとして表示されている 値を実行時間として採用すること。 mは分、sは秒を表すので、上の例では40.606秒ということになる。
提出ファイル | ICPC2007a.java |
---|---|
コメント欄: | Sample Inputに対する実行結果 |
提出先: | 「宿題提出Web:アルゴリズムA:課題2b」 http://ynitta.com/class/algoB/local/handin/up.php?id=kadai2b |
次の問題を解くプログラム ICPC2007a.java を作成しなさい。
もしもソートが必要ならば、今回作成した InsertSortクラスの
InsertSort.sort(int[])
メソッドを利用すること。
世界道化コンテスト (International Clown and Pierrot Competition; ICPC) は興行界で権威も人気も最高の行事である.
このコンテストの特色のひとつは,採点に当たる審判員の数が多いことで, ときには百人にも上る. 審判の数は競技者ごとに異なる. というのは,採点対象の競技者と少しでも関係のある審判は, その競技者の演技の採点から一時的に外れるからである.
基本としては,ひとりの競技者の演技についての審判の点数の平均が その競技者の点数になる. 常軌を逸した視点から採点する審判が点数に大きな影響を与えないよう, 「最高点側から3人の点」と「最低側から3人の点」は除外する. 平均点には端数があるかもしれないが,それは切り捨てて最終的な点数は 整数値とする.
この行事をテレビ中継向けにスピードアップするため,ある演技の点数を 審判全員の採点から計算するプログラム ICPC2007a.java を書くことを, あなたは頼まれた.
入力はそれぞれが競技者の演技ひとつに対応するいくつかのデータセットからなる. 入力のデータセット数は20以下である.
データセットの最初の行はある演技の採点に当たった審判の数 $n ~~$ (ただし、$ 7 \leqq n \leqq 100$ ) である。 引き続く $n$ 行には各審判のつけた点数 $s_i~~$ (ただし $ 0 \leqq s \leqq 1000$, $~~1 \leqq i \leqq n$ ) がひとつずつ入っている. $n$ も各 $s_i$ も整数である. 入力中にはこれらの数を表すための数字以外の文字はない.審判名は秘匿されている.
入力の終わりは $0$ がひとつ含まれた行で示される.
出力は,入力データセットごとにそのデータセットに対応する演技の 点数を十進整数で記した一行である.出力行には他の文字があってはならない.
|
|
提出ファイル | ICPC2016qa.java |
---|---|
コメント欄: | なし |
提出先: | 「宿題提出Web:アルゴリズムA:課題2c」 http://ynitta.com/class/algoA/local/handin/up.php?id=kadai2c |
次の問題を解くプログラム ICPC2016qa.java を作成しなさい。 入力 A1.txt に対する 出力が A1ans.txt と同一になることを確認したら、 プログラムを提出しなさい。
ICPC2016qa.javaの実行例 |
|
もしもソートが必要ならば、今回作成した InsertSortクラスの
InsertSort.sort(int[])
メソッドを利用すること。
筑波博士は,プログラミング教育の新しい方法を考案した。 この方法が有効かどうかを確認するために,対照実験を行うことにした。 2 人の学生を被験者として,一方を従来の方法で教え,もう一方を新しい方法で教える。 2 人の最終的な成績を比べれば,新しい方法が有効かどうか判定できるだろう。
公平な比較を行うためには,成績のなるべく近い 2 人を選ぶことが肝要である。 手元には,実験に参加可能な学生各人の成績の一覧表がある。 この中から成績の差が最も小さい 2 人を選ぶプログラムを書いてほしい.
入力は複数のデータセットからなる. 各データセットは次の形式で表される.
$~~~~ 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$ を超えない.
各データセットについて,成績の差が最小の 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 |