1. 序章

このチュートリアルでは、Javaでシェルソートアルゴリズムについて説明します。

2. シェルソートの概要

2.1. 説明

まず、シェルソートアルゴリズムについて説明して、実装しようとしているものを把握しましょう。

シェルソートは挿入ソートアルゴリズムに基づいており、非常に効率的なアルゴリズムのグループに属しています。 一般に、アルゴリズムは元のセットをより小さなサブセットに分割し、次にそれらのそれぞれが挿入ソートを使用してソートされます。

しかし、それがサブセットをどのように作成するかは簡単ではありません。 予想されるように、サブセットを形成するために隣接する要素を選択しません。 むしろ、シェルソートはサブセットの作成にいわゆるインターバルまたはギャップを使用します。 たとえば、ギャップ I がある場合、1つのサブセットに 要素 つまり、Iの位置が離れています。

まず、アルゴリズムは互いに遠く離れている要素を並べ替えます。 次に、ギャップが小さくなり、より近い要素が比較されます。 このようにして、正しい位置にない一部の要素は、隣接する要素からサブセットを作成した場合よりも速く配置できます。

2.2. 例

これを、ギャップが3と1で、ソートされていない9つの要素のリストがある例で見てみましょう。

上記の説明に従うと、最初の反復では、3つの要素を持つ3つのサブセットがあります(同じ色で強調表示されています)。

最初の反復で各サブセットを並べ替えると、リストは次のようになります。

ソートされたリストはまだありませんが、要素が目的の位置に近づいていることに注意してください。

最後に、1ずつ増やしてもう1つソートする必要があります。これは、実際には基本的な挿入ソートです。 リストをソートするために実行する必要のあるシフト操作の数は、最初の反復を実行しなかった場合よりも少なくなりました。

2.3. ギャップシーケンスの選択

すでに述べたように、シェルソートにはギャップシーケンスを選択する独自の方法があります。 これは難しい作業であり、ギャップが少なすぎたり多すぎたりしないように注意する必要があります。 詳細については、最も提案されているギャップシーケンスリストを参照してください。

3. 実装

それでは、実装を見てみましょう。 間隔の増分には、シェルの元のシーケンスを使用します。

N/2, N/4, …, 1 (continuously dividing by 2)

実装自体はそれほど複雑ではありません。

public void sort(int arrayToSort[]) {
    int n = arrayToSort.length;

    for (int gap = n / 2; gap > 0; gap /= 2) {
        for (int i = gap; i < n; i++) {
            int key = arrayToSort[i];
            int j = i;
            while (j >= gap && arrayToSort[j - gap] > key) {
                arrayToSort[j] = arrayToSort[j - gap];
                j -= gap;
            }
            arrayToSort[j] = key;
        }
    }
}

最初にforループを使用してギャップシーケンスを作成し、次にギャップサイズごとに挿入ソートを実行しました。

これで、メソッドを簡単にテストできます。

@Test
public void givenUnsortedArray_whenShellSort_thenSortedAsc() {
    int[] input = {41, 15, 82, 5, 65, 19, 32, 43, 8};
    ShellSort.sort(input);
    int[] expected = {5, 8, 15, 19, 32, 41, 43, 65, 82};
    assertArrayEquals("the two arrays are not equal", expected, input);
}

4. 複雑

一般に、シェルソートアルゴリズムは中規模のリストで非常に効率的です。 複雑さはギャップシーケンスに大きく依存するため決定が困難ですが、時間計算量は O(N) O(N ^ 2)の間で異なります。

最悪の場合のスペースの複雑さは、 O(N) O(1)補助スペースです。

5. 結論

このチュートリアルでは、シェルソートについて説明し、Javaでそれを実装する方法を示しました。

いつものように、コード全体はGitHubにあります。