アルゴリズムA 第13回


整列

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

注意

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

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

計算量

オーダーソートの種類
O(n2)バブルソート、選択ソート、挿入ソート
O(n1.5)シェルソート
O(n log n)クイックソート、ヒープソート、マージソート

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

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

安定な整列

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

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

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

Javaのクラス

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


単純な整列アルゴリズム

計算量がO(n2)の整列アルゴリズム3種類。

選択ソート

選択ソートのアルゴリズム 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 (読み込んだデータを小さい順に並べ変える)
授業で配布するプリントを参照して下さい。
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> 


アルゴリズムA 演習


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

課題13a: 選択ソート

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

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

SelectionSort.java (メソッドに分ける)
import java.util.*;
public class SelectionSort {
    static boolean debug = false;
    public static void main(String[] args) {
	if (args.length > 0 && args[0].equals("-d")) debug = true;
	Scanner sc = new Scanner(System.in); // 標準入力から読み込む
	System.out.print("データの個数を入力して下さい  ");
	int n = sc.nextInt();	// データの個数を読み込む
	int[] a = new int[n];	// データを保持する配列を作る
	for (int i=0; i<n; i++) a[i] = sc.nextInt(); // n個のデータを入力する
	sort(a);
	System.out.println(toString(a));
    }
    public static void sort(int[] a) { // 小さい順に整列する

	// [課題] この部分を自分で考えて書きましょう。
	//        debugがtrueの時は途中経過を出力することに注意して下さい。

    }
    public static String toString(int[] a) { // データを文字列にして返す

	// [課題] この部分を自分で考えて書きましょう。
        //        StringBufferを使うのが適切な方法でしょう。

    }
}
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              ←結果の出力

課題13b: 中央値

提出先 http://nw.tsuda.ac.jp/class/algoA/local/handin/list.php?id=kadai13b
提出ファイルGetMedian.java
コメント欄:intdata01.txt, intdata02.txt, intdata03.txt を処理した結果

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

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

[入力形式]
  N
  D1
  D2
  ...
  DN

Nはデータの個数を表す自然数。 Di は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