挿入ソート insert sort
2020-09-12
こんにちは、0371です。
今回は、SQLのお勉強をしたいと思います。
今回は、挿入ソートの方法について書いていきます。
基本情報技術者試験のアルゴリズムの問題集から、擬似言語の問題を実際の言語でプログラミングしてみました。
挿入ソート とは？
整列されている配列に、追加の要素を適切な位置に挿入するソート。
挿入ソートを行うプログラム
言語はJavaです。
Main.java
import java.util.ArrayList;
import java.util.Collections;
import java.util.Random;
public class Main {
public static void main(String[] args) {
int listsize = 5;
int range = 10;
ArrayList<Integer> list = new ArrayList<>();
Random rand = new Random();
for(int i=0; i<listsize; i++)list.add(rand.nextInt(range));
Collections.sort(list);
int addInt = rand.nextInt(range);
System.out.println("配列の末尾に追加する数値: "+addInt);
list.add(addInt);
System.out.println("整列前の配列: "+list);
System.out.println();
InsertSort(list);
System.out.println();
System.out.println("整列後の配列: "+list);
}
private static void InsertSort(ArrayList<Integer> list) {
boolean loop = true; // ループ継続条件
int lis_j = 0; // 探索の範囲
int tmp = 0; // 一時変数
int outCount = 1; // 外側ループカウンター
int inCount = 1; // 内側ループカウンター
for (int lis_i = 0; lis_i < list.size(); lis_i++) {
System.out.println("=== "+outCount+++"回目の外ループ ===");
System.out.println("["+lis_i+"]から探索します。");
tmp = list.get(lis_i);
System.out.println("tmp: "+tmp);
lis_j = lis_i - 1;
loop = true;
while(lis_j >= 0 && loop == true) {
System.out.println("--- "+inCount+++"回目の内ループ ---");
System.out.println("tmp: "+tmp);
System.out.println("["+lis_j+"]の"+list.get(lis_j)+"と比較します。");
if(list.get(lis_j) > tmp) {
System.out.println("tmpの"+tmp+"よりも"+list.get(lis_j)+"が大きいので、"+"["+(lis_j+1)+"]に "+list.get(lis_j)+"を代入します。");
list.set(lis_j+1, list.get(lis_j));
lis_j = lis_j - 1;
} else {
System.out.println("探索を終了します。");
loop = false;
}
}
inCount = 1;
list.set(lis_j+1, tmp);
System.out.println(tmp+"を["+(lis_j+1)+"]に格納します。");
System.out.println();
}
}
}
確認なしverはこちら
import java.util.ArrayList;
import java.util.Collections;
import java.util.Random;
public class Main {
public static void main(String[] args) {
int listsize = 5;
int range = 10;
ArrayList<Integer> list = new ArrayList<>();
Random rand = new Random();
for(int i=0; i<listsize; i++)list.add(rand.nextInt(range));
Collections.sort(list);
int addInt = rand.nextInt(range);
list.add(addInt);
System.out.println("整列前の配列: "+list);
System.out.println();
InsertSort(list);
System.out.println();
System.out.println("整列後の配列: "+list);
}
private static void InsertSort(ArrayList<Integer> list) {
boolean loop = true; // ループ継続条件
int lis_j = 0; // 探索の範囲
int tmp = 0; // 一時変数
for (int lis_i = 0; lis_i < list.size(); lis_i++) {
tmp = list.get(lis_i);
lis_j = lis_i - 1;
loop = true;
while(lis_j >= 0 && loop == true) {
if(list.get(lis_j) > tmp) {
list.set(lis_j+1, list.get(lis_j));
lis_j = lis_j - 1;
} else {
loop = false;
}
}
list.set(lis_j+1, tmp);
}
}
}
InsertSort()メソッドの中では、追加された要素をどこに格納するかの判断を行っています。
loopがfalseになるか、添字の要素が0以下になるまで、比較のループを行います。
確認ありverで、実行した結果は以下の通りです。
配列の末尾に追加する数値: 4
整列前の配列: [0, 1, 3, 6, 8, 4]
=== 1回目の外ループ ===
[0]から探索します。
tmp: 0
0を[0]に格納します。
=== 2回目の外ループ ===
[1]から探索します。
tmp: 1
--- 1回目の内ループ ---
tmp: 1
[0]の0と比較します。
探索を終了します。
1を[1]に格納します。
=== 3回目の外ループ ===
[2]から探索します。
tmp: 3
--- 1回目の内ループ ---
tmp: 3
[1]の1と比較します。
探索を終了します。
3を[2]に格納します。
=== 4回目の外ループ ===
[3]から探索します。
tmp: 6
--- 1回目の内ループ ---
tmp: 6
[2]の3と比較します。
探索を終了します。
6を[3]に格納します。
=== 5回目の外ループ ===
[4]から探索します。
tmp: 8
--- 1回目の内ループ ---
tmp: 8
[3]の6と比較します。
探索を終了します。
8を[4]に格納します。
=== 6回目の外ループ ===
[5]から探索します。
tmp: 4
--- 1回目の内ループ ---
tmp: 4
[4]の8と比較します。
tmpの4よりも8が大きいので、[5]に 8を代入します。
--- 2回目の内ループ ---
tmp: 4
[3]の6と比較します。
tmpの4よりも6が大きいので、[4]に 6を代入します。
--- 3回目の内ループ ---
tmp: 4
[2]の3と比較します。
探索を終了します。
4を[3]に格納します。
整列後の配列: [0, 1, 3, 4, 6, 8]
成功していますね。
今日の一言
アルゴリズム初心者だと、ちょっと何やってるかわからんっすね〜(白目)