シェルソート

1. シェルソートアルゴリズム
2. シェルのソート例
3. シェルソートアルゴリズムの実装
4. シェルソートアルゴリズムの複雑さ

シェルソートは、高効率な比較ベースのソートアルゴリズムです。これは、バブルソートアルゴリズムの一般化、または最適化された挿入ソートアルゴリズムと見られています。挿入ソートアルゴリズムでは、要素を 1つ前の位置に移動させます。しかし、シェルソートの場合は、要素を h 位置前方に移動させます。これは、非常に遠い要素をソートすることから始まり、配列全体をソートするためのシーケンスに基づいて徐々にギャップを減らしていきます。使用されているシーケンスの一部を紹介します。

シェルソートアルゴリズム

ここでは、n 要素を含むソートされていない配列 A[] があるとしましょう。この配列をソートするために、シェルの元のシーケンスを利用します。

シェルのソート例

配列 （9、8、3、7、5、6、4、1）があるとします。シェルソートアルゴリズムを用いてソートし、シェルの元の配列を用いてギャップ間隔を小さくします。

• 最初の繰り返し

n/2 = 4 の場合、間隔 4 にある要素を比較して交換します。

A[0] > A[4] →スワップ、(5,8,3,7,9,6,4,1).

A[1] > A[5] →スワップ、(5,6,3,7,9,8,4,1).

A[2] < A[6]

A[3] > A[7] → スワップ、(5,6,3,1,9,8,4,7)

配列は以下のようになります：(5,6,3,1,9,8,4,7)。

• 2 回目の繰り返し

n/4 = 2 の場合、間隔 2 にある要素を比較して交換します。

A[0] > A[2] →スワップ、(3,6,5,1,9,8,4,7)

A[1] > A[3] →スワップ、(3,1,5,6,9,8,4,7)

A[0] < A[2] < A[4]

A[1] < A[3] < A[5]

A[2] > A[4] と A[4] > A[6] →スワップ、(3,1,4,6,5,8,9,7)。

A[1] < A[3] < A[5] が、A[5] > A[7] → スワップ、(3,1,4,6,5,7,9,8)

配列は次のようになります： （3,1,4,6,5,7,9,8）。

• 3 回目の繰り返し

n/8 = 1 の場合、間隔 1 にある要素を比較して交換します。

A[0] > A[1] → スワップ (1,3,4,6,5,7,9,8)

A[0] ... A[2] → ソート済み

A[0] ... A[3] → ソート済み

A[0] ... A[3] →ソートされたが、A[3] > A[4] → スワップ、(1,3,4,5,6,7,9,8)

A[0] ... A[5] → ソート済み

A[0] ... A[6] → ソート済み

A[0] ... A[6] → ソートされたが、A[6] > A[7] → スワップ、(1, 3, 4, 5, 6, 7, 8, 9)

シェルソートアルゴリズムの実装

#include <bits/stdc++.h>
using namespace std;
void shellSort(int arr[], int n) {
  for (int gap = n / 2; gap > 0; gap /= 2) {
    for (int i = gap; i < n; i += 1) {
      int temp = arr[i];
      int j;
      for (j = i; j >= gap && arr[j - gap] > temp; j -= gap)
        arr[j] = arr[j - gap];
      arr[j] = temp;
    }
  }
}
int main() {
  int n = 8;
  int arr[8] = {9, 8, 3, 7, 5, 6, 4, 1};
  cout << "Input arr: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
  shellSort(arr, n);  // Sort elements in ascending order
  cout << "Output arr: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
}

シェルソートアルゴリズムの複雑さ

時間計算量

• 平均のケース

複雑さはソートのために選択されたシーケンスに依存します。時間的な複雑さは [Big Theta]：O(nlog(n)²)のオーダーです。

• 最悪のケース

シェルソートの最悪の時間的複雑さは常に O(n²)以下です。より正確には Poonen の定理によれば、θ(nlogn)²/(log log n)²)またはθ(nlog n)²/log log n)またはθ(n(log n)²)またはその間の何かで与えられます。最悪の場合の時間的複雑さは [Big O]：O(n²)以下です。

• 最良のケース

ベストケースは、配列が既にソートされていて、各区間に必要な比較が配列のサイズと同じである場合に発生します。最良の時間的複雑さは [Big　Omega]: O(nlogn) です。

空間計算量

シェルソートアルゴリズムの空間複雑度は O(n) です。