package j1.lesson11basic;
import java.io.*;
/**
* 課題1115 - 解答例.
* @author java2005
* @version $Id: SelectionSort_java.rps,v 1.1 2006/07/14 05:33:59 java2005 Exp $
*/
public class SelectionSort {
/**
* コンソールから実数型のデータを次々と入力し、選択ソートと呼ばれる方法でデータを小さい順に並べ替える過程を表示するプログラム。
* 選択ソートは、最小値を順に求めて（選択して）、それを並べていく方法である。
* <ol>
* <li> 最初に配列data全体の中から最小値を求めて、それを配列の先頭（0番目、すなわちdata[0]）に置き、
* もともと先頭にあったものを最小値があった場所（課題1112ではindexOfMinimum番目）に移す（配列の先頭と最小値を入れ替える）。
* これで、配列の0番目に最小値が入り、1番目以降にはそれより小さくない値が入る。 </li>
* <li> 次に、同じことを配列の1番目以降に対して行って、1番目以降での最小値を1番目に入れる。 </li>
* <li> 以下同様のことを繰り返して行って、最後に、配列dataのdata.length-2番目と
* data.length-1番目の小さなほうをdata.length-2番目に入れたら、ソートが完成する。 </li>
* </ol>
* mainメソッドの動作を表す擬似コードは以下の通りである。
* <pre><code>
* プログラム全体
* print "データ個数を入力："
* dataSize = コンソール入力 (整数)
* if dataSize が0以下
* print "データ個数は、1以上にして下さい。"
* プログラムの終了
* data = 長さ dataSize の新しい配列 (double[])
* for i を 0 から dataSize - 1 まで
* print "第" + i + "番目のデータを入力:"
* data[i] = コンソール入力(実数)
* // 選択ソートの開始
* for n を 0 から data.length-2 まで
* // 配列のn番目とn番目に小さい値を持つ配列要素を以下のようにして入れ換える
* // (0番目に小さい値は最小値)
* // n-1番目まではソート済みなので、n番目以降の最小値が全体のn番目に小さい値になる。
* // その値 nthMinとインデックスindexOfNthMinを求める（この部分は課題1112参照）
* // n番目のデータがn番目に小さい値になるように，データを入れ換える
* // すなわち、data[n]とdata[indexOfNthMin]（=nthMin）を入れ替える。
* (ここの部分、上記6行に渉るコメントに相当する擬似コードを省略した。じっくり考えてみよう。)
* // 様子が分かるようにここで出力
* for i を 0 から data.length-1 まで
* print data[i] + " "
* </code></pre>
* @param args 無視される
* @throws IOException 入力時に例外が発生した場合
*/
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
// データの個数を入力する
System.out.print("データの個数を入力：");
int dataSize = Integer.parseInt(reader.readLine());
if (dataSize <= 0) {
System.out.print("データの個数は、1以上にして下さい。");
return;
}
// データを入力する
double[] data = new double[dataSize];
for (int i = 0; i < data.length; i++) {
System.out.print("第" + i + "番目のデータを入力：");
data[i] = Double.parseDouble(reader.readLine());
}
// 選択ソートの開始
// 配列のn番目とn番目に小さい値を持つ配列要素を入れ換える(0番目に小さい値は最小値)
for (int nthMin = 0; nthMin < data.length; nthMin++) {
// n-1番目まではソート済みなので、n番目以降の最小値が全体のn番目に小さい値になる。その値とインデックスを求める
int indexOfMinimum = nthMin;
double minimum = data[indexOfMinimum];
for (int i = nthMin; i < data.length; i++) {
if (data[i] < minimum) {
indexOfMinimum = i;
minimum = data[indexOfMinimum];
}
}
// n番目のデータがn番目に小さい値になるように，データを入れ換える
// n番目のデータをn番目に小さい値がある場所に退避
data[indexOfMinimum] = data[nthMin];
// n番目のデータをn番目に小さい値で書き換える
data[nthMin] = minimum;
// 様子が分かるようにここで出力
for (int i = 0; i < data.length; i++) {
System.out.print(data[i] + " ");
}
System.out.println();
}
// 結果だけならここで，出力
// for(int i=0; i < data.length; i++){
// System.out.print(data[i]+" ");
// }
}
}
|