Edited at

Javaで選択ソート

More than 5 years have passed since last update.

今回は選択ソートです。

名前の通り、選択した値とその他の値全てと比較し、ソートしていく方法です。


解法


  • 配列 6 4 5 3 1 2

並び替えの順序は


  • まず先頭の数値 6 のarray[0] を keyIndex として保持する


  • array[key] > 4で4の方が小さいので、4のarray[1]のindex番号をkeyIndexとして保持する


  • array[key] > 4で4の方が小さいので、4のarray[1]をindex番号keyIndexとして保持する


  • array[key] > 5で5の方が大きいので何もしない


  • array[key] > 3で3の方が小さいので、3のarray[3]をindex番号keyIndexとして保持する


  • array[key] > 1で1の方が小さいので、1のarray[4]をindex番号keyIndexとして保持する


  • array[key] > 2で2の方が大きいので何もしない


  • 比較が終わったので、array[keyIndex]とarray[0]の値を入れ替える


  • 6 4 5 3 1 2 -> 1 4 5 3 6 2 の状態になります。


  • array[1]をkeyIndexとして保持します。

    ・・・省略



選択ソート

package aoj.sort;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class SelectionSort {
public static void main(String args[]) throws IOException {
// aojの問題を解く際の入力の受付なので無視して下さい。
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int elementNum = Integer.parseInt(br.readLine());
String line = br.readLine();
int[] numArray = parseInt(getSplitLine(line));

// ここから選択ソート
int count = 0;
for (int i = 0; i < numArray.length - 1; i++) {
// 比較元の配列番号をセットする
int keyIndex = i;
// 最小値を探索する
// keyIndexで指定された最小値と配列に含まれる数値全てを比較し、
// 最小値が見つかれば、keyIndexへ最小値をセットする
for (int j = i + 1; j < numArray.length; j++) {
if (numArray[keyIndex] > numArray[j]) {
// 最少値 numArray[keyIndex] と numArray[j]を比較し、numArray[j]の方が小さければ、
// 最少値として設定する
keyIndex = j;
}
}
// 最小値が入れ替わっていなければ数値の入れ替えをスキップ
if (i == keyIndex) {
continue;
}
//
int temp = numArray[i];
numArray[i] = numArray[keyIndex];
numArray[keyIndex] = temp;
count++;
}

System.out.println(Arrays.toString(numArray)
.replaceAll("[\\[\\],]", ""));
System.out.println(count);
}

private static String[] getSplitLine(String line) {
return line.split("\\s");
}

private static int[] parseInt(String[] line) {
int[] numArray = new int[line.length];
for (int i = 0; i < line.length; i++) {
numArray[i] = Integer.parseInt(line[i]);
}
return numArray;
}
}