0371.blog

挿入ソート insert sort

code

こんにちは、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]

成功していますね。

今日の一言

アルゴリズム初心者だと、ちょっと何やってるかわからんっすね〜(白目)