データ (レコードと呼ぶことがあります) の集まりを、 キーの値の大小関係によって並べ換える操作。
比較によらない整列もある(デジタルソート→教科書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参照)
単純な整列アルゴリズムである
「選択ソート」、「バブルソート」、「挿入ソート」
のうち、選択ソートは「安定な整列」ではありませんが、
「バブルソート」と「挿入ソート」は「安定な整列」です。
選択ソートが安定でないことは
一般に、「単純で遅い→安定」、「複雑で速い→安定でない」傾向があります。 しかし、「本来のキー」以外に「データの元の位置」をサブキーとして使い、 「本来のキー」が等しいときはサブキーを比較するようにすれば、 (余分なキーの比較というオーバーヘッドは発生するが)本来「安定でない」 アルゴリズムを「安定」として使うことができます。
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]と交換する。以下同様に続ける。 |
一般に左端の i 個の要素の整列が終った状態では、 i 〜 n-1 の範囲で最小の値を持つ a[k] を探し、 a[i] と a[k] を交換すればよいことがわかるでしょう。
この方針に基づいて Sort1.java を作成してみましょう。 入力データは、整数とし、まず最初にデータの個数が 入力されるものとします。
Sort1.javaの実行例 |
|
作成したプログラムが正しく動作することを確認したら、それぞれの 提出先に提出しなさい。
提出した後は、正しく提出されていることを http://ynitta.com/class/algoB/local/handin/ で必ず確認しておいて下さい。
課題提出〆切は、次回の授業開始時刻です。
提出先 | 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の実行例 |
|
提出先 | 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_i$ は $0$ 以上 $100$ 以下の整数。
出力は入力データの中央値。 余分な "$.0$" を出力しても構わないものとする。 すなわち、下の実行例で "$70$" が "$70.0$" に、"$65$" が "$65.0$" と出力されていても構わない。 (ただし、余分な"$.0$"を出力しないプログラムの方が高く評価される。)
|
|
|
|