1.概要

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

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

私たちは空の左手から始めて、カードをテーブルの上に置きました。

その後、テーブルからカードを1枚ずつ取り除き、左側の正しい位置にそれを挿入します。新しいカードの正しい位置を見つけるために、それを手の中ですでにソートされたカードのセットと右から左に比較します。

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

2.擬似コード

私たちは挿入ソートのための擬似コードを

INSERTION-SORT

と呼ばれる手続きとして提示し、ソートされるべきn個のアイテムの配列

A[1 .. 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

の項目は

key

と呼ばれます。

keyを取得すると、アルゴリズムの2番目の部分は正しいインデックスを見つけることを扱います。



key

がインデックス

j__の項目の値よりも小さい場合、キーは1つ左の位置に移動します キーよりも小さい要素に到達した場合まで、プロセスは続きます。

インデックス

i



key

の正しい位置を見つけるための反復を開始する前に、配列

A[1 .. j – 1]

はすでに__ソート済みであることに注意することが重要です。

3.命令実装

必須の場合は、整数の配列をパラメータとして、

挿入

SortImperative__という関数を作成します。

関数は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.再帰的な実装

再帰的な場合のための関数は

挿入ソート再帰的

と呼ばれ、整数の配列を入力として受け取ります(命令型の場合と同じ)。

ここでの必須のケースとの違いは(再帰的であるという事実にもかかわらず)、ソートする項目の数に等しい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項目を超える入力シーケンスをソートするときは非効率になります。

二次的な複雑さにもかかわらず、それは

merge sort

の場合のように補助スペースを必要とせずにその場でソートすることを覚えておいてください。

コード全体はhttps://github.com/eugenp/tutorials/tree/master/algorithms-sorting[GitHubに載って]を見つけることができます。