Javaでのシェルソート

1. 前書き

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

2. シェルソートの概要

2.1. 説明

最初にシェルのソートアルゴリズムを説明して、実装しようとしているものがわかるようにします。
シェルソートはlink:/java-insertion-sort[Insertion sort algorithm]に基づいており、非常に効率的なアルゴリズムのグループに属します。 一般的に、*アルゴリズムは元のセットをより小さなサブセットに分割し、それぞれが挿入ソート*を使用してソートされます。

2.2. 例

link:/uploads/Screen-Shot-2019-07-22-at-11.10.24-PM-100x10.png%20100w []
link:/uploads/Screen-Shot-2019-07-22-at-11.12.28-PM-100x10.png%20100w []
link:/uploads/Screen-Shot-2019-07-22-at-11.13.29-PM-100x9.png%20100w []
ソートされたリストはまだありませんが、要素は望ましい位置に近づいていることに注意してください。
link:/uploads/Screen-Shot-2019-07-22-at-11.43.27-PM-100x71.png%20100w []

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. 複雑

一般的に、* Shellソートアルゴリズムは中規模のリストで非常に効率的です*。 複雑さはギャップシーケンスに大きく依存するため決定するのは困難ですが、時間の複雑さは_O(N)_と_O(N ^ 2)_の間で異なります。
最悪の場合の空間の複雑さは、_O(N)_と_O(1)_補助空間です。

5. 結論

このチュートリアルでは、シェルソートについて説明し、それをJavaで実装する方法を示しました。
いつものように、コード全体はhttps://github.com/eugenp/tutorials/tree/master/algorithms-sorting[GitHubで]にあります。