Javaで挿入ソート：わかりやすい例とステップバイステップガイド

挿入ソートアルゴリズムとは

挿入ソートは、小さなデータセットやほぼソート済みのデータセットに適したシンプルなソート手法です。各反復で要素を1つ取り出し、直前の要素と比較しながら、適切な位置に挿入します。

挿入ソートは最悪・平均ケースでO(n²)の時間計算量ですが、配列がすでにソート済みの場合は線形時間で動作します。インプレースで安定なソートであり、追加メモリは定数しか必要としません。

挿入ソートのプロセス

挿入ソートのワークフローを視覚的に表現:

挿入ソートアルゴリズムのプロセス

挿入ソートで配列をソートするJavaプログラム例

package com.guru99;
public class InsertionSortExample {
    public static void main(String a[]) {
        int[] myArray = {860, 8, 200, 9};
        System.out.println("挿入ソート前");
        printArray(myArray);
        insertionSort(myArray); // 挿入ソートで配列をソート
        System.out.println("挿入ソート後");
        printArray(myArray);
    }
    
    public static void insertionSort(int arr[]) {
        int n = arr.length;
        for (int i = 1; i < n; i++) {
            System.out.println("ソートパス番号 " + (i));
            int key = arr[i];
            int j = i - 1;
            while ((j > -1) && (arr[j] > key)) {
                System.out.println("比較: " + key + " と " + arr[j]);
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
            System.out.println("要素を交換: 交換後の配列");
            printArray(arr);
        }
    }
    
    static void printArray(int[] array) {
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + " ");
        }
        System.out.println();
    }
}

コードの出力:

挿入ソート前
860 8 200 9
ソートパス番号 1
比較: 8 と 860
要素を交換: 交換後の配列
8 860 200 9
ソートパス番号 2
比較: 200 と 860
要素を交換: 交換後の配列
8 200 860 9
ソートパス番号 3
比較: 9 と 860
比較: 9 と 200
要素を交換: 交換後の配列
8 9 200 860
挿入ソート後
8 9 200 860