シェルソート

Harshit Jindal 2023年10月12日
  1. シェルソートアルゴリズム
  2. シェルのソート例
  3. シェルソートアルゴリズムの実装
  4. シェルソートアルゴリズムの複雑さ
シェルソート

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

シェル独自のシーケンス N/2, N/4,..., 1
パペルノフ&スタセビッチ 1, 3, 5, 9,...
ヒバード 1, 3, 7, 15, 31, 63,...
クヌート 1, 4, 13, ... , (3k – 1) / 2
プラット 1, 2, 3, 4, 6, 9, 8, 12, 18, 27, 16, ....
セッジウィック 1, 8, 23, 77, 281, ... 4j+1+3-2j+1

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

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

  • シーケンスに従って gap の値を計算します。
  • gap と等しい間隔の各部分配列について、以下のようにします。
  • 挿入ソートを用いてソートします。
  • 配列が完全にソートされるまで上記の処理を繰り返します。

シェルのソート例

配列 (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)2)のオーダーです。

  • 最悪のケース

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

  • 最良のケース

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

空間計算量

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

著者: Harshit Jindal
Harshit Jindal avatar Harshit Jindal avatar

Harshit Jindal has done his Bachelors in Computer Science Engineering(2021) from DTU. He has always been a problem solver and now turned that into his profession. Currently working at M365 Cloud Security team(Torus) on Cloud Security Services and Datacenter Buildout Automation.

LinkedIn

関連記事 - Sort Algorithm