挿入ソート

一昔前なら当たり前にソートアルゴリズムを自分で書いていたらしいのですが、
自分世代だとJavaのコレクションクラスで既に用意してくれていたりします。
自前で書こうものならコードレビューでお叱りを受けるでしょう。
とは言え、じゃあ実際に書けるのかと言われれば

どうやんだっけ？

そもそも挿入ソートってなんだっけ？

となってしまうのは、学生時代に習った数学を忘れたサラリーマンならありがちだと思います。
※調べりゃ出来るってのはありますが。

前置きが長くなりましたが基本を思い出すことで新しい発想に繋げる為にも
今一度勉強していきます。
※人に説明できて初めて本質的に理解しているとも言いますし。

挿入ソートのコード

import java.io.IOException;
import java.util.Arrays;
import java.util.Scanner;
public class InsertionSort {
    public static void main(String args[]) throws IOException {
        @SuppressWarnings("resource")
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int A[] = new int[n];
        for (int i = 0; i < n; i++) {
            A[i] = scanner.nextInt();
        }
        System.out.println(Arrays.toString(A).replaceAll("[,\\[\\]]", ""));
        // ここから挿入ソート
        for (int j = 1; j < A.length; j++) {
            int key = A[j];
            int i = j - 1;
            while (i >= 0 && A[i] > key) {
                A[i + 1] = A[i];
                i--;
            }
            A[i + 1] = key;
            System.out.println(Arrays.toString(A).replaceAll("[,\\[\\]]", ""));
        }
    }
}

解法

array[5] = { 5, 2, 4, 1, 6, 3}
のような配列があった場合、以下のようにソートをしていきます。
サンプルコードを見ながら読み進めてもらえると理解しやすいと思います。

・5 > 2 // 1番目と２番目の要素を比較
-> 5, 5, 4, 1, 6, 3 // int key = A[j];
-> 2, 5, 4, 1, 6, 3 // A[i + 1] = key;
・5 > 4 // 2番目と3番目の要素を比較
-> 2, 5, 5, 1, 6, 3 // int key = A[j];
-> 2, 4, 5, 1, 6, 3 // A[i + 1] = key;
・5 > 1 // 3番目と4番目の要素を比較
-> 2, 4, 5, 5, 6, 3 // int key = A[j];　
-> 2, 4, 4, 5, 6, 3 // int key = A[j];
-> 2, 2, 4, 5, 6, 3 // int key = A[j];
-> 1, 2, 4, 5, 6, 3 // A[i + 1] = key;
・・・・後は省略
こんな感じで手前の要素と比較し、手前の要素の方が大きければ、
数値を先頭まで比較し入れ替え、最後に先頭となった要素へ数値を入れていきます。

Javaで挿入ソート

挿入ソート

挿入ソートのコード

解法