挿入ソートアルゴリズムの理解 (Java の例付き)

挿入ソートは、反復的なソート アルゴリズムです。ソートされていない各要素をソートされた部分配列内の正しい位置に挿入することにより、一度に 1 要素ずつソートされたサブ配列を構築します。 トランプの手札を並べ替えることを考えてください。並べ替えた 1 枚のカードから始めて、後続の各カードを、すでに並べ替えられたカードの適切な場所に挿入します。

挿入ソートの仕組み

昇順に並べ替える配列の例を示します。

最初の反復:

最初の要素はすでにソートされているとみなします。 アルゴリズムは 2 番目の要素から始まります。

2

2 番目の反復:

6 をソートされた部分配列 (2, 8) と比較します。 6

このプロセスは、配列全体がソートされるまで続きます。

Java での実装

import java.util.Arrays;

public class InsertionSortTest {
    public static void main(String[] args) {
        int[] arr = {8, 2, 6, 4, 9, 1};
        System.out.println("Unsorted array: " + Arrays.toString(arr));
        insertionSort(arr);
        System.out.println("Sorted array: " + Arrays.toString(arr));
    }

    public static void insertionSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int key = arr[i];
            int j = i - 1;
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
        }
    }
}

コードは各要素を key として繰り返します。 次に、key とソートされた部分の要素を比較し、key の正しい位置が見つかるまで、より大きな要素を右にシフトします。

たとえば、2 番目の反復 (i=2) では次のようになります。

key は 6 です。while ループは、正しい位置が見つかるまで要素をシフトします。

最後に 6 が挿入されます:

出力:

ソートされていない配列: [8, 2, 6, 4, 9, 1] ソートされた配列: [1, 2, 4, 6, 8, 9]

複雑さの分析

• 時間計算量:
  • ベストケース (O(n)): すでにソートされた配列。
  • 平均ケース (O(n²)): ランダムに配置された要素。
  • 最悪の場合 (O(n²)): 逆ソートされた配列。
• 空間複雑度: O(1) (インプレース アルゴリズム)

結論

挿入ソートの二次時間計算量により、大規模なデータセットの場合は非効率的になります。 ただし、これは単純なアルゴリズムであり、小さなデータセットまたはほぼ並べ替えられたデータに対して適切に実行されます。

以上が挿入ソートアルゴリズムの理解 (Java の例付き)の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。