こんにちは。「Javaを復習する初心者」です。
今回はソートの交換法、選択法、挿入法を書いてみました。参考にしたのは日経ソフトウェア2017年4月号に載っていた「トランプでおぼえるアルゴリズム」です。C言語で載っていたのをJavaにして、整列の途中経過を出力するようにしました。
交換法
交換法という名前で紹介されてましたが、バブルソートという言い方の方が一般的かもしれません。今回紹介された方法では、横一列に数を並べたとして、一番右側から順に、左隣の数より小さいかを判定するという方法です。もし左隣の数が大きいなら互いに交換します。次に右から2番目からという風に走査します。
ソース
package nikkei201704;
import java.util.Arrays;
public class Sort1 {
public static void main(String[] args) {
int[] nums = { 6, 4, 7, 5, 3};
System.out.println(Arrays.toString(nums));
for (int i = 0; i <= nums.length - 2; i++) {
for (int j = nums.length - 1; j >= i + 1; j--) {
if (nums[j - 1] > nums[j]) {
int temp = nums[j - 1];
nums[j - 1] = nums[j];
nums[j] = temp;
}
System.out.println(Arrays.toString(nums));
}
}
}
}結果
[6, 4, 7, 5, 3]
[6, 4, 7, 3, 5]
[6, 4, 3, 7, 5]
[6, 3, 4, 7, 5]
[3, 6, 4, 7, 5]
[3, 6, 4, 5, 7]
[3, 6, 4, 5, 7]
[3, 4, 6, 5, 7]
[3, 4, 6, 5, 7]
[3, 4, 5, 6, 7]
[3, 4, 5, 6, 7]「5, 3」が最初に交換されます。3は一番小さい数なのでどんどん左側に移動することになります。繰り返しカウンタiが0のとき、最終的に3が一番右に移動します。繰り返し変数iが1のとき、繰り返し変数jは要素数 – 1からi + 1まで変化させます。nums[i]に最小値を格納するためです。iが1以上時、nums[i – 1]までは左から昇順で整列されているので、繰り返し変数jはi + 1まで変化させれば十分です。
選択法
選択法は一番左側から最小値を置く位置を仮定して、右側の各数と比較していく方法です。
ソース
package nikkei201704;
import java.util.Arrays;
public class Sort2 {
public static void main(String[] args) {
int[] nums = { 6, 4, 7, 5, 3};
System.out.println(Arrays.toString(nums));
for (int i = 0; i <= nums.length - 2; i++) {
int minPos = i;
for (int j = i + 1; j <= nums.length - 1; j++) {
if (nums[minPos] > nums[j]) {
minPos = j;
}
}
int temp = nums[i];
nums[i] = nums[minPos];
nums[minPos] = temp;
System.out.println(Arrays.toString(nums));
}
}
}結果
[6, 4, 7, 5, 3]
[3, 4, 7, 5, 6]
[3, 4, 7, 5, 6]
[3, 4, 5, 7, 6]
[3, 4, 5, 6, 7]繰り返しカウンタiが0のとき、一番左の「6」の位置が最小であると仮定しています。右側の数と比較し、右側の方が小さい場合、その位置を仮の交換先とします。最終的に「3」が最小なのでこの位置と最初の位置にある数を交換します。
挿入法
交換法と似ていますが、左からi番目までで数の比較をするというところが交換法と手順が違う個所のようです。
ソース
package nikkei201704;
import java.util.Arrays;
public class Sort3 {
public static void main(String[] args) {
int[] nums = { 6, 4, 7, 5, 3};
System.out.println(Arrays.toString(nums));
for (int i = 1; i <= nums.length - 1; i++) {
for (int j = i; j >= 1; j--) {
if (nums[j - 1] > nums[j]) {
int temp = nums[j - 1];
nums[j - 1] = nums[j];
nums[j] = temp;
System.out.println(Arrays.toString(nums));
} else {
break;
}
}
}
}
}結果
[6, 4, 7, 5, 3]
[4, 6, 7, 5, 3]
[4, 6, 5, 7, 3]
[4, 5, 6, 7, 3]
[4, 5, 6, 3, 7]
[4, 5, 3, 6, 7]
[4, 3, 5, 6, 7]
[3, 4, 5, 6, 7]一番右の位置にある数「3」は最初のうちは位置はそのままです。3より左側が昇順に「4, 5, 6, 7」となった時に、「3」を入れ替えていく処理が実行されます。「3」が右端に残ったままなのは、繰り返しカウンタiに対して、nums[i]から左側へ交換作業を繰り返すやり方だからです。
速さ比較の一例
上記の3つのプログラムの速さを比較してみました。整列対象の配列は共通していますが、一例でしかないので、比較結果は一例ということになります。
ソース
package nikkei201704;
import java.util.Arrays;
import java.util.function.Supplier;
public class Test {
// --計測用--
private void printProcessingTime(Supplier<String> f) {
int count = 300000;
long start, end;
start = System.currentTimeMillis();
for (int i = 0; i < count; i++) {
f.get();
}
end = System.currentTimeMillis();
System.out.printf("出力確認:%s, 計測 %3d: ", f.get(), end - start);
System.out.println();
}
public static void main(String[] args) {
new Test().test();
}
private void test() {
System.out.println("交換法");
printProcessingTime(() -> {
int[] nums = { 6, 4, 7, 5, 3};
for (int i = 0; i <= nums.length - 2; i++) {
for (int j = nums.length - 1; j >= i + 1; j--) {
if (nums[j - 1] > nums[j]) {
int temp = nums[j - 1];
nums[j - 1] = nums[j];
nums[j] = temp;
}
}
}
return Arrays.toString(nums);
});
System.out.println("選択法");
printProcessingTime(() -> {
int[] nums = { 6, 4, 7, 5, 3};
for (int i = 0; i <= nums.length - 2; i++) {
int minPos = i;
for (int j = i + 1; j <= nums.length - 1; j++) {
if (nums[minPos] > nums[j]) {
minPos = j;
}
}
int temp = nums[i];
nums[i] = nums[minPos];
nums[minPos] = temp;
}
return Arrays.toString(nums);
});
System.out.println("挿入法");
printProcessingTime(() -> {
int[] nums = { 6, 4, 7, 5, 3};
for (int i = 1; i <= nums.length - 1; i++) {
for (int j = i; j >= 1; j--) {
if (nums[j - 1] > nums[j]) {
int temp = nums[j - 1];
nums[j - 1] = nums[j];
nums[j] = temp;
} else {
break;
}
}
}
return Arrays.toString(nums);
});
}
}結果
交換法
出力確認:[3, 4, 5, 6, 7], 計測 113:
選択法
出力確認:[3, 4, 5, 6, 7], 計測 121:
挿入法
出力確認:[3, 4, 5, 6, 7], 計測 105: 途中結果の出力を削除して、各300000回繰り返しました。挿入法が一番速いという結果になりましたが、それほど大きな差はありませんでした。並び変えの対象とする配列をもっと大きくしたから結果が変わるかもしれません。