【Java】挿入ソート

挿入ソートとは

挿入ソートとは、要素を挿入しながら配列やリストをソートするアルゴリズムの1つです。
挿入ソートは、ソートアルゴリズムの中では、構造が単純であり実装が容易です。反面、計算量が多い場合や効率性が重視される場合には、効率が悪くなることがあります。

問題の内容と回答の方針等

• 問題
  • サイズnの数列aを挿入ソートせよ。
• 条件
  • 配列の最初の要素を整列済みと見なす。
• 解答方針
  • 数列aを配列a[]で管理します。
  • i回目にa[i]を、合計n-1回挿入します。但し、iの初期値を1とします。
  • アルゴリズムにより要素a[i]は消えてしまうので、要素a[i]を変数xに保存します。
  • 変数xを入れる場所を探す変数jをi-1で初期化します。
  • 変数jが0以上、かつ、a[j] > xである間、a[j]を右にずらし、jを1減らすことを繰り返します。
  • a[j + 1]に変数x代入します。
• 今回の入力値
  上からn、aとする。

  4
  8 1 3 2
  

挿入ソートのコード例

import java.util.*;

public class Main {
    static void print(int[] a, int n) {
        for (int i = 0; i < n; i++) {
            if (i > 0)
                System.out.print(" ");
            System.out.print(a[i]);
        }
        System.out.println();
    }

    static void insertionSort(int[] a, int n) {
        for (int i = 1; i < n; i++) {

            // 変数xに配列の要素a[i]を保存する。
            int x = a[i];
            // 変数jに配列のインデックスiから1引いたものを代入する。（インデックスj=i-1番目）
            int j = i - 1;
            
            // インデックスjが0以上、かつ、要素a[j]が変数xより大きい間
            while (j >= 0 && a[j] > x) {
                // 要素a[j+1]に要素a[j]をコピーする。（a[j]を1つ右にずらす）
                a[j + 1] = a[j];
                // jを1減らす
                j--;
            }

            // 要素a[j+1]に変数xを挿入する。
            a[j + 1] = x;

            print(a, n);
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }

        insertionSort(a, n);
    }
}

---

挿入ソートアルゴリズムの解説

挿入ソートアルゴリズムに該当する下記の部分のみを解説します。

static void insertionSort(int[] a, int n) {
    for (int i = 1; i < n; i++) {

        int x = a[i];

        int j = i - 1;
        
        while (j >= 0 && a[j] > x) {
            a[j + 1] = a[j];
            j--;
        }

        a[j + 1] = x;

        print(a, n);
    }
}

仮引数は下記の通りです。

a = [8, 1, 3, 2]
n = 4

---

i = 1 の場合

1. for文の条件式i=1 < n=4を満たすので、
2. 変数xに、配列の要素a[1]の1を代入します。
3. 変数jに、i - 1の0を代入します。
4. while文の条件式j=0 >= 0を満たし、かつ、a[j]=8 > x=1を満たすので、
5. 要素a[j + 1]に要素a[j]=8を代入します。
   この時の配列aは下記の通りになります。

   a = [8, 8, 3, 2]
   

   一旦、配列の要素a[1]の1は消えてしまいます。
6. 変数jは-1となるので、while文の条件を満たさないので、このループを抜けます。
7. a[-1 + 1]は、a[0]となるので、これに変数xの1を代入します。
   この時の配列aは下記の通りになります。

   a = [1, 8, 3, 2]
   

8. printメソッドを呼び出し、実引数として配列aと変数nを渡します。

---

i = 2 の場合

1. for文の条件式i=2 < n=4を満たすので、
2. 変数xに、配列の要素a[2]の3を代入します。
3. 変数jに、i - 1の1を代入します。
4. while文の条件式j=1 >= 0を満たし、かつ、a[j]=8 > x=3を満たすので、
5. 要素a[j + 1]に要素a[j]=8を代入します。
   この時の配列aは下記の通りになります。

   a = [1, 8, 8, 2]
   

   一旦、配列の要素a[2]の3は消えてしまいます。
6. 変数jは0となるので、while文の条件j=0 >= 0を満たしますが、a[j]=1 > x=3を満たさないので、このループを抜けます。
7. a[0 + 1]は、a[1]となるので、これに変数xの3を代入します。
   この時の配列aは下記の通りになります。

   a = [1, 3, 8, 2]
   

8. printメソッドを呼び出し、実引数として配列aと変数nを渡します。

---

i = 3 の場合

1. for文の条件式i=3 < n=4を満たすので、
2. 変数xに、配列の要素a[3]の2を代入します。
3. 変数jに、i - 1の2を代入します。
4. while文の条件式j=2 >= 0を満たし、かつ、a[j]=8 > x=2を満たすので、
5. 要素a[j + 1]に要素a[j]=8を代入します。
   この時の配列aは下記の通りになります。

   a = [1, 3, 8, 8]
   

   一旦、配列の要素a[3]の2は消えてしまいます。
6. 変数jは1となるので、while文の条件j=1 >= 0を満たし、かつ、a[j]=3 > x=2を満たすので、
7. 要素a[j + 1]に要素a[j]=3を代入します。
   この時の配列aは下記の通りになります。

   a = [1, 3, 3, 8]
   

8. 変数jは0となるので、while文の条件j=0 >= 0を満たしますが、a[j]=1 > x=3を満たさないので、このループを抜けます。
9. a[0 + 1]は、a[1]となるので、これに変数xの2を代入します。
   この時の配列aは下記の通りになります。

   a = [1, 2, 3, 8]
   

10. printメソッドを呼び出し、実引数として配列aと変数nを渡します。

これで、ようやく配列aがソートされました。