Zenn
🎯

【Java】シェルソート

2024/03/13に公開
Java
初心者
tech

シェルソートとは

シェルソートとは、挿入ソートの改良版であり、大きな配列を小さな間隔列に分割し、それぞれの間隔列を挿入ソートでソートします。その後、間隔列の間隔を縮小しながら間隔が1になるまで再度ソートを行います。
シェルソートの性能は間隔列に大きく依存し、間隔列の選択によってソートの速度が大きく変わります。しかし、間隔列の最適解は未解決です。
シェルソートは、挿入ソート・選択ソート・バブルソートよりも効率的なソートアルゴリズムであり、比較的に実装が簡単であり、数千から数万の要素を持つ中程度のサイズのデータセットに対して効果的です。

問題の内容

  • 問題
    • サイズnの数列aをサイズkの間隔列hでシェルソートせよ。
    n = 10
a = 7 6 10 2 5 4 8 3 9 1
k = 2
h = 4 1

言語によるシェルソートアルゴリズム

数列aと間隔列hは下記の通りです。

a: 7 6 10 2 5 4 8 3 9 1
h: 4 1

最初の間隔である4を使って、数列aを部分的にソートします。つまり、4個おきに要素をグループ分けして、それぞれのグループ内で挿入ソートを行います。

グループ1: 7, 5, 9
グループ2: 6, 4, 1
グループ3: 10, 8
グループ4: 2, 3

これらのグループ内で挿入ソートを行うと、以下のようになります。

グループ1: 5, 7, 9
グループ2: 1, 4, 6
グループ3: 8, 10
グループ4: 2, 3

それぞれのグループを元の位置に戻すと、数列は以下のようになります。

a = 5, 1, 8, 2, 7, 4, 10, 3, 9, 6

次に、間隔1を使って、数列aを部分的にソートします。これは通常の挿入ソートになります。

a = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

これで、数列aは完全にソートされました。
間隔列hに基づいて、部分的にソートされた配列が生成され、最後のステップでは通常の挿入ソートが適用されました。

コードによるシェルソートアルゴリズム

  • 解答方針
    • 間隔hは、h[0]からh[k-1]まで
    • hからn-1までのインデックスiについて、a[i]を挿入
    • アルゴリズムによりa[i]が消えてしまうので、a[i]を変数xに保存
    • 変数xを入れるインデックスを探すための変数jをi-hで初期化
    • a[j] > xである間、a[j]をhだけ右にずらす
    • a[j + h]にxを代入

シェルソートのコード例

import java.util.*;

public class Main {

    static void insertionSort(int[] a, int n, int h) {
        int numOfMove = 0;

        // インデックス i が h から n - 1 までのループ
        for (int i = h; i < n; i++) {
            // 要素 a[i] を x に保存する
            int x = a[i];
            // 変数 x を入れるインデックスを探すための変数 j = i-h で初期化
            int j = i - h;
            // インデックス j が 0 以上で、要素 a[j] が x より大きい間
            while (j >= 0 && a[j] > x) {
                // 要素 a[j] を h だけ右にずらす
                a[j + h] = a[j];
                // インデックス j を h だけ減らす
                j -= h;
                numOfMove++;
            }

            // 要素 a[j + h] に x を代入する
            a[j + h] = x;
        }

        System.out.println(numOfMove);
    }

    static void shellSort(int[] a, int n, int[] h, int k) {
    for (int i = 0; i < k; i++) {
        // 間隔 h の挿入ソートを呼び出す
        insertionSort(a, n, h[i]);
    }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }

        int k = sc.nextInt();

        int[] h = new int[k];
        for (int i = 0; i < k; i++) {
            h[i] = sc.nextInt();
        }

        shellSort(a, n, h, k);
    }
}

シェルソートアルゴリズムの解説

シェルソートアルゴリズムに該当する下記の部分のみを解説します。

static void insertionSort(int[] a, int n, int h) {
    int numOfMove = 0;

    for (int i = h; i < n; i++) {
        int x = a[i];
        int j = i - h;

        while (j >= 0 && a[j] > x) {
            a[j + h] = a[j];
            j -= h;
            numOfMove++;
        }
        a[j + h] = x;
    }
    System.out.println(numOfMove);
}

static void shellSort(int[] a, int n, int[] h, int k) {
for (int i = 0; i < k; i++) {
    insertionSort(a, n, h[i]);
}
}

仮引数a、n、h、kは下記の通りになります。

a = [7, 6, 10, 2, 5, 4, 8, 3, 9, 1]
n = 10
h = [4, 1]
k = 2

shellSortメソッド

まずは、shellSortメソッドについて解説します。

  1. for文の条件式i=0 < k=2を満たすので、
  2. insertionSortメソッドを呼び出し、実引数としてa、n、h[0]=4を渡します。
  3. iを1増やして、for分の条件式i=1 < k=2を満たすので、
  4. insertionSortメソッドを呼び出し、実引数としてa、n、h[1]=1を渡します。
  5. iを1増やして、for分の条件式i=2 < k=2を満たさないので、shellSortメソッドを終了します。

要は、ここでは、間隔4でinsertionSortメソッドを呼び出し、次に、間隔1でinsertionSortメソッドを呼び出しています。

insertionSortメソッド

上記の通りinsertionSortメソッドは2回呼び出されますので、2回に分けて解説します。

1回目のinsertionSortメソッド呼び出し

1回目のinsertionSortメソッド呼び出しは、シェルソートそのものと言っても過言ではありません。
仮引数は下記の通りです。

a = [7, 6, 10, 2, 5, 4, 8, 3, 9, 1]
n = 10
h = 4
  1. 変数numOfMoveを0で初期化します。
  2. for文の条件式i=4 < n=10を満たすので、
  3. 変数xにa[4]の5を代入し保存します。
  4. 変数jにi=4 - h=4の0を代入します。
  5. while文の条件式j=0 >= 0 かつ a[0]=7 > 5を満たすので、
  6. a[4]にa[0]の7を代入します。
  7. 変数jにj=0 - h=4の-4を代入し更新します。
  8. numOfMoveを1に更新します。
  9. while文の条件式j=-4 >= 0を満たさないので、このループを抜けます。
  10. a[0]に変数xの5を代入します。
    この時の配列aは下記の通りです。
    a = [5, 6, 10, 2, 7, 4, 8, 3, 9, 1]
  11. iに1を加えて、for文の条件式i=5 < n=10を満たすので、
  12. 変数xにa[5]の4を代入し保存します。
  13. 変数jにi=5 - h=4の1を代入します。
  14. while文の条件式j=1 >= 0 かつ a[1]=6 > 4を満たすので、
  15. a[5]にa[1]の6を代入します。
  16. 変数jにj=1 - h=4の-3を代入し更新します。
  17. numOfMoveを2に更新します。
  18. while文の条件式j=-3 >= 0を満たさないので、このループを抜けます。
  19. a[1]に変数xの4を代入します。
    この時の配列aは下記の通りです。
    a = [5, 4, 10, 2, 7, 6, 8, 3, 9, 1]
  20. iに1を加えて、for文の条件式i=6 < n=10を満たすので、
  21. 変数xにa[6]の8を代入し保存します。
  22. 変数jにi=6 - h=4の2を代入します。
  23. while文の条件式j=2 >= 0 かつ a[2]=10 > 8を満たすので、
  24. a[6]にa[2]の10を代入します。
  25. 変数jにj=2 - h=4の-2を代入し更新します。
  26. numOfMoveを3に更新します。
  27. while文の条件式j=-2 >= 0を満たさないので、このループを抜けます。
  28. a[2]に変数xの8を代入します。
    この時の配列aは下記の通りです。
    a = [5, 4, 8, 2, 7, 6, 10, 3, 9, 1]
  29. iに1を加えて、for文の条件式i=7 < n=10を満たすので、
  30. 変数xにa[7]の3を代入し保存します。
  31. 変数jにi=7 - h=4の3を代入します。
  32. while文の条件式j=3 >= 0 かつ a[3]=2 > 3を満たさないので、このループを抜けます。
  33. a[7]に変数xの3を代入します。(元々、a[7]=3です。)
    この時の配列aに変更はありません。
  34. iに1を加えて、for文の条件式i=8 < n=10を満たすので、
  35. 変数xにa[8]の9を代入し保存します。
  36. 変数jにi=8 - h=4の4を代入します。
  37. while文の条件式j=4 >= 0 かつ a[4]=7 > 9を満たさないので、このループを抜けます。
  38. a[8]に変数xの9を代入します。(元々、a[8]=9です。)
    この時の配列aに変更はありません。
  39. iに1を加えて、for文の条件式i=9 < n=10を満たすので、
  40. 変数xにa[9]の1を代入し保存します。
  41. 変数jにi=9 - h=4の5を代入します。
  42. while文の条件式j=5 >= 0 かつ a[5]=6 > 1を満たすので、
  43. a[9]にa[5]の6を代入します。
  44. 変数jにj=5 - h=4の1を代入し更新します。
  45. numOfMoveを4に更新します。
  46. while文の条件式j=1 >= 0 かつ a[1]=4 > 1を満たすので、
  47. a[5]にa[1]の4を代入します。
  48. 変数jにj=1 - h=4の-3を代入し更新します。
  49. numOfMoveを5に更新します。
  50. while文の条件式j=-3 >= 0を満たさないので、このループを抜けます。
  51. a[1]に変数xの1を代入します。
    この時の配列aは下記の通りです。
    a = [5, 1, 8, 2, 7, 4, 10, 3, 9, 6]

これで、言語によるシェルソートアルゴリズムのグループ内で挿入ソートを行い、元の位置に戻した結果と同じになりました。

2回目のinsertionSortメソッド呼び出し

2回目のinsertionSortメソッド呼び出しは、挿入ソートと全く同じですので、少しだけ解説をして、残りの解説については割愛します。
仮引数は下記の通りです。

a = [5, 1, 8, 2, 7, 4, 10, 3, 9, 6]
n = 10
h = 1
  1. 変数numOfMoveを0で初期化します。
  2. for文の条件式i=1 < n=10を満たすので、
  3. 変数xにa[1]の1を代入し保存します。
  4. 変数jにi=1 - h=1の0を代入します。
  5. while文の条件式j=0 >= 0 かつ a[0]=5 > 1を満たすので、
  6. a[1]にa[0]の5を代入します。
  7. 変数jにj=0 - h=4の-4を代入し更新します。
  8. numOfMoveを1に更新します。
  9. while文の条件式j=-4 >= 0を満たさないので、このループを抜けます。
  10. a[0]に変数xの1を代入します。
    この時の配列aは下記の通りです。
    a = [1, 5, 8, 2, 7, 4, 10, 3, 9, 6]
    1回目のinsertionSortメソッド呼び出しと同じように、このような作業を繰り返して、最終的に配列aは下記のようにソートされます。
    a = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

Discussion