Javaでの挿入ソート

投稿日: 2019-10-18 2022-10-25
タグ: Core Java, Java

1. 概要

このチュートリアルでは、挿入ソートアルゴリズムについて説明し、そのJava実装を見ていきます。

挿入ソートは、少数のアイテムを注文するための効率的なアルゴリズムです。この方法は、カードプレーヤーがトランプの手を並べ替える方法に基づいています。

空の左手とテーブルに置かれたカードから始めます。次に、テーブルから一度に1枚のカードを取り出し、左手の正しい位置に挿入します。新しいカードの正しい位置を見つけるために、右から左に、手札にあるすでにソートされているカードのセットと比較します。

擬似コード形式のアルゴリズムステップを理解することから始めましょう。

2. 擬似コード

挿入ソート用の擬似コードを、というプロシージャとして提示します。 挿入ソート 、パラメータとして配列を取ります A[1。。 n] ソートされるn個のアイテムの。 アルゴリズムは、入力配列をインプレースで並べ替えます（配列A内の項目を再配置することにより）。

手順が終了すると、入力配列Aには入力シーケンスの順列が含まれますが、並べ替えられた順序になります。

INSERTION-SORT(A)

for i=2 to A.length
    key = A[i]
    j = i - 1 
    while j > 0 and A[j] > key
        A[j+1] = A[j]
        j = j - 1
    A[j + 1] = key

上記のアルゴリズムについて簡単に説明します。

インデックスiは、処理する配列内の現在のアイテムの位置を示します。

定義上、1つの項目を持つ配列はソートされていると見なされるため、2番目の項目から開始します。インデックスiのアイテムは、キーと呼ばれます。 キーを取得すると、アルゴリズムの2番目の部分は、正しいインデックスの検索を処理します。 キーがインデックスjのアイテムの値よりも小さい場合、キーは1つ左に移動します。このプロセスは、キーよりも小さい要素に到達するまで続きます。

の正しい位置を見つけるための反復を開始する前に、注意することが重要です。鍵インデックスで私、配列 A[1。。 j – 1] もうソート済み 。

3. 命令型の実装

命令型の場合、整数の配列をパラメーターとして使用して、insertionSortImperativeという関数を記述します。関数は、2番目の項目から配列の反復を開始します。

反復中の任意の時点で、この配列は論理的に2つの部分に分割されていると考えることができます。左側は並べ替えられたもので、右側はまだ並べ替えられていないアイテムを含みます。

ここで重要なのは、新しいアイテムを挿入する正しい位置を見つけた後、アイテムを右にシフト（交換ではなく）して、スペースを空けることです。

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

次に、上記のメソッドのテストを作成しましょう。

@Test
public void givenUnsortedArray_whenInsertionSortImperative_thenSortedAsc() {
    int[] input = {6, 2, 3, 4, 5, 1};
    InsertionSort.insertionSortImperative(input);
    int[] expected = {1, 2, 3, 4, 5, 6};
    assertArrayEquals("the two arrays are not equal", expected, input);
}

上記のテストは、アルゴリズムが入力配列の昇順で正しく並べ替えられることを証明します <6、2、3、4、5、1> 。

4. 再帰的な実装

再帰的な場合の関数はinsertionSortR ecursive と呼ばれ、整数の配列を入力として受け入れます（命令型の場合と同じ）。

ここでの命令型の場合との違いは（再帰的であるにもかかわらず）、は、ソートする項目の数に等しい2番目の引数を持つオーバーロードされた関数を呼び出すことです。

配列全体を並べ替えたいので、その長さに等しい数のアイテムを渡します。

public static void insertionSortRecursive(int[] input) {
    insertionSortRecursive(input, input.length);
}

再帰的なケースはもう少し難しいです。 1つのアイテムで配列を並べ替えようとすると、基本ケースが発生します。この場合、何もしません。

後続のすべての再帰呼び出しは、入力配列の事前定義された部分を並べ替えます– 2番目の項目から始まり、配列の最後に到達するまで：

private static void insertionSortRecursive(int[] input, int i) {
    if (i <= 1) {
        return;
    }
    insertionSortRecursive(input, i - 1);
    int key = input[i - 1];
    int j = i - 2;
    while (j >= 0 && input[j] > key) {
        input[j + 1] = input[j];
        j = j - 1;
    }
    input[j + 1] = key;
}

そして、これは6項目の入力配列の呼び出しスタックがどのように見えるかです。

insertionSortRecursive(input, 6)
insertionSortRecursive(input, 5) and insert the 6th item into the sorted array
insertionSortRecursive(input, 4) and insert the 5th item into the sorted array
insertionSortRecursive(input, 3) and insert the 4th item into the sorted array
insertionSortRecursive(input, 2) and insert the 3rd item into the sorted array
insertionSortRecursive(input, 1) and insert the 2nd item into the sorted array

それのテストも見てみましょう：

@Test
public void givenUnsortedArray_whenInsertionSortRecursively_thenSortedAsc() {
    int[] input = {6, 4, 5, 2, 3, 1};
    InsertionSort.insertionSortRecursive(input);
    int[] expected = {1, 2, 3, 4, 5, 6};
    assertArrayEquals("the two arrays are not equal", expected, input);
}

上記のテストは、アルゴリズムが入力配列の昇順で正しく並べ替えられることを証明します <6、2、3、4、5、1> 。

5. 時間と空間の複雑さ

INSERTION-SORTプロシージャの実行にかかる時間はO（n ^ 2）です。新しいアイテムごとに、配列の既に並べ替えられた部分を右から左に繰り返して、正しい位置を見つけます。次に、アイテムを1つ右にシフトして挿入します。

アルゴリズムは適切に並べ替えられるため、スペースの複雑さは命令型実装の場合はO（1）、再帰的実装の場合はO（n）になります。

6. 結論

このチュートリアルでは、挿入ソートを実装する方法を見ました。

このアルゴリズムは、少数のアイテムを並べ替える場合に役立ちます。 100項目を超える入力シーケンスをソートする場合は非効率になります。

二次の複雑さにもかかわらず、マージソートの場合のように、補助スペースを必要とせずにその場でソートすることに注意してください。

コード全体は、GitHubでにあります。

getdocs

13036