アルゴリズムb 第1回


整列

データ (レコードと呼ぶことがあります) の集まりを、 キーの値の大小関係によって並べ換える操作。

注意

比較によらない整列もある(デジタルソート→教科書17章)。 この方法の整列には、 binソート、分布数え上げソート、基数ソートなどがある。 キーの範囲をある範囲に限定すると、 計算量が $O(n)$ となるものも存在する。

ちなみに、比較による整列では最速のアルゴリズムでも $O( n \log n )$ かかる。

計算量

オーダーソートの種類
$O(n^2)$ バブルソート、選択ソート、挿入ソート
$O(n^{1.5})$ シェルソート
$O(n \log n )$ クイックソート、ヒープソート、マージソート

nの値に応じて、次のように使い分けるとよいらしい。

$n$使うとよい、ソートの種類
小さいとき単純なソート
$1000$ 程度シェルソート
大きいときクイックソート

安定な整列

「安定な整列」=「整列するデータの中に同じキーを持つものがあったとき、 それらの順番が整列後でも保たれる」。(p.287, Fig.11.2参照)

単純な整列アルゴリズムである 「選択ソート」、「バブルソート」、「挿入ソート」 のうち、選択ソートは「安定な整列」ではありませんが、 「バブルソート」と「挿入ソート」は「安定な整列」です。 選択ソートが安定でないことは8 5 5 2 1のような5個のデータを昇順(小さい順)に整列する状況を考えればわかります。

一般に、「単純で遅い→安定」、「複雑で速い→安定でない」傾向があります。 しかし、「本来のキー」以外に「データの元の位置」をサブキーとして使い、 「本来のキー」が等しいときはサブキーを比較するようにすれば、 (余分なキーの比較というオーバーヘッドは発生するが)本来「安定でない」 アルゴリズムを「安定」として使うことができます。

Javaのクラス

java.util.Arraysクラスは「配列」を扱うためのクラスだが、 昇順に並べ変えるsort()メソッドが用意されていている。


単純な整列アルゴリズム

選択ソート(p.297)、バブルソート(p.294)、挿入ソート(p.300)の3種類が単純なソート $O(n^2)$ です。 選択ソートに関して今回説明します。

選択ソート

選択ソートのアルゴリズム p.297
        n個の値  a[0], a[1], ..., a[n-1] を並べ替えるには、まず全体を
	見渡してその中で最小のものを見つけ、それをa[0]と交換する。
        つぎに、a[1],a[2],...,a[n-1]の中で最小のものを見つけ、それを
        a[1]と交換する。以下同様に続ける。
  1. n個の要素を持つ配列があるとします


  2. インデックスが 0 〜 n-1 の範囲で最小の値を持つ a[k] を探します。そして、a[0] と a[k] を交換します。


  3. 左端の1個要素だけが整列が終った状態になります。


  4. インデックスが 1 〜 n-1 の範囲で最小の値を持つ a[k] を探します。そして、a[1] と a[k] を交換します。


  5. 左端の2個の要素だけが整列が終った状態になります。


  6. これを」繰り返します。
  7. 最終的に全体の整列が終った状態になります。


一般に左端の i 個の要素の整列が終った状態では、 i 〜 n-1 の範囲で最小の値を持つ a[k] を探し、 a[i] と a[k] を交換すればよいことがわかるでしょう。



この方針に基づいて Sort1.java を作成してみましょう。 入力データは、整数とし、まず最初にデータの個数が 入力されるものとします。




Sort1.javaの実行例
sp204: ~/pro 4> javac Sort1.java 
sp204: ~/pro 5> java Sort1 
データの個数を入力して下さい  8 
5 8 7 9 2 7 1 3 
1 2 3 5 7 7 8 9         ←小さい順に表示される
sp204: ~/pro 6> 


アルゴリズムb 演習


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

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

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

課題1a: 選択ソート

提出先 http://ynitta.com/class/algoB/local/handin/list.php?id=kadai1a
提出ファイルSelectionSort.java
コメント欄:コマンド引数に-dを指定して"4 3 7 1 9 6 0 2 8 5"という10個の整数をソートした場合の実行結果

Sort1.javaにおいて「配列内のデータを整列」させる部分や「配列内のデータを表示」 させる部分をメソッドにしたプログラムを作成して下さい。 これらのメソッドへの引数としては、処理すべき配列を渡すことになります。 ファイル名は SelectionSort.javaとして下さい。




SelectionSort.javaの実行例
$ javac SelectionSort.java   
$ java SelectionSort   
データの個数を入力して下さい  8   
5 8 7 9 2 7 1 3               ←入力データ
1 2 3 5 7 7 8 9            ←結果の出力 
$ java SelectionSort -d       ←コマンド引数に-dをつけて実行すると
データの個数を入力して下さい  8   
5 8 7 9 2 7 1 3               ←入力データ
sorting: 1 8 7 9 2 7 5 3   ←途中結果を出力する  
sorting: 1 2 7 9 8 7 5 3 
sorting: 1 2 3 9 8 7 5 7 
sorting: 1 2 3 5 8 7 9 7 
sorting: 1 2 3 5 7 8 9 7 
sorting: 1 2 3 5 7 7 9 8 
sorting: 1 2 3 5 7 7 8 9 
1 2 3 5 7 7 8 9              ←結果の出力

課題1b: 中央値

提出先 http://ynitta.com/class/algoB/local/handin/list.php?id=kadai1b
提出ファイルGetMedian.java
コメント欄:intdata01.txt, intdata02.txt, intdata03.txt を処理した結果

複数の整数値を入力として、中央値(median)を出力するプログラムを書きなさい。

[注] 中央値 (median)とは、有限個のデータを小さい順に並べたとき中央に位置する値である。 たとえば5人の人がいるとき、その5人の年齢の中央値は3番目に年寄りな人の年齢である。 ただし、データが偶数個の場合は、中央に近い2つの値の算術平均をとる。

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

[入力形式]
$~~~~ N$
$~~~~ D_1$
$~~~~ D_2$
$~~~~ \cdots$
$~~~~ D_N$

$N$ はデータの個数を表す自然数。 $D_i$ は $0$ 以上 $100$ 以下の整数。

出力は入力データの中央値。 余分な "$.0$" を出力しても構わないものとする。 すなわち、下の実行例で "$70$" が "$70.0$" に、"$65$" が "$65.0$" と出力されていても構わない。 (ただし、余分な"$.0$"を出力しないプログラムの方が高く評価される。)
intdata01.txt
5
80
30
70
90
40
intdata02.txt
6
80
30
70
90
40
60
intdata03.txt
6
80
30
70
90
40
65
GetMedian.javaの実行例
$ javac GetMedian.java 
$ java GetMedian < intdata01.txt 
70
$ java GetMedian < intdata02.txt 
65
$ java GetMedian < intdata03.txt 
67.5