シェルソートアルゴリズムと例
サラ・チェン
シェルソートとは
シェルのメソッド、つまりデータ構造におけるシェル ソートは、効率的なインプレース比較ソート アルゴリズムです。 この名前は、ドナルド シェルが 1959 年に最初のアイデアを提案したときに付けられました。シェル ソートは、挿入ソート アルゴリズムを一般化した拡張です。
このソート アルゴリズムの基本的な考え方は、離れた要素をグループ化し、それに従ってソートすることです。その後、要素間のギャップを徐々に狭めます。シェル ソートは、離れた要素を比較して交換することで、挿入ソートの平均的なケース時間の複雑さを克服します。
間隔として知られるこのギャップは、いくつかの最適なギャップ シーケンスに従って減少します。 シェルソートの実行時間もこれらのシーケンスに依存します。 シェルのオリジナル シーケンス、クヌースの公式、ヒバードのインクリメントなど、いくつかのギャップ シーケンスがあります。シェルのオリジナルのギャップ シーケンスは – n/2, n/4, n/8, ……….1
シェルソートアルゴリズム
シェルソートアルゴリズムのステップまたは手順は次のとおりです。
ステップ1） 間隔値を初期化します (h = n/2)。 (この例では、n は配列のサイズです)
ステップ2） 間隔 h の距離内にあるすべての要素をサブリストに入れます。
ステップ3） 挿入ソートを使用してこれらのサブリストをソートします。
ステップ4） 新しい間隔、h=h/2 を設定します。
ステップ5） h>0 の場合はステップ 2 に進みます。それ以外の場合はステップ 6 に進みます。
ステップ6） 結果の出力はソートされた配列になります。
シェルソートの仕組み
挿入ソートでは、要素は一度に XNUMX 位置だけ移動します。 それに対して、シェルソートは間隔値に基づいて配列をより小さな部分に分割し、それらの部分に対して挿入ソートを実行します。
徐々に間隔の値が減少し、分割されたピースのサイズが増加します。 ピースは事前に個別にソートされているため、これらのピースをマージする場合に必要な手順は、 挿入ソート.
次の GIF は、シェル ソートのデモを示しています。このデモでは、挿入ソートに基づいて、赤と青で示された値を比較して交換します。次に、間隔が狭くなり、シェル ソートは、ほぼソートされたデータで挿入ソートを開始します。
シェルソートアルゴリズムの仕組み
シェル ソート アルゴリズムの次の例を見てみましょう。この例では、シェル ソートを使用して次の配列をソートします。
ステップ1） ここでは、配列サイズは 8 です。したがって、間隔値は h = 8/2 または 4 になります。
ステップ2） ここで、すべての要素を距離 4 に保存します。この場合、サブリストは {8, 1}、{6, 4}、{7, 5}、{2, 3} です。
ステップ3） ここで、これらのサブリストは挿入ソートを使用してソートされます。挿入ソートでは、一時変数を使用して両方の数値を比較し、それに応じてソートします。
スワップ操作後の配列は次のようになります。
ステップ4） ここで、間隔の初期値を減少させます。 新しい間隔は h=h/2 または 4/2 または 2 になります。
ステップ5） 2>0 なので、ステップ 2 に進み、すべての要素を距離 2 に保存します。今回のサブリストは次のとおりです。
{1、5、8、7}、{4、2、6、3}
次に、これらのサブリストは挿入ソートを使用してソートされます。最初のサブリストを比較して交換した後、配列は次のようになります。
XNUMX 番目のサブリストを並べ替えると、元の配列は次のようになります。
そうするとまた間隔が短くなります。 ここで、間隔は h=h/2 または 2/1 または 1 になります。 したがって、挿入ソート アルゴリズムを使用して、変更された配列をソートします。
以下は挿入ソートの手順を段階的に説明したものです。
間隔は再び 2 で除算されます。この時点までに間隔は 0 になります。そのため、ステップ 6 に進みます。
ステップ6） 間隔が 0 であるため、配列はこの時間でソートされます。 ソートされた配列は-
疑似コード
Start
Input array an of size n
for (interval = n / 2; interval & gt; 0; interval /= 2)
for (i = interval; i & lt; n; i += 1)
temp = a[i];
for (j = i; j & gt; = interval & amp; & amp; a[j - interval] & gt; temp; j -= interval)
a[j] = a[j - interval];
a[j] = temp;
End
C言語のシェルソートプログラム/C++
入力：
//Shell Sort Program in C/C++
#include <bits/stdc++.h>
using namespace std;
void ShellSort(int data[], int size) {
for (int interval = size / 2; interval > 0; interval /= 2) {
for (int i = interval; i < size; i += 1) {
int temp = data[i];
int j;
for (j = i; j >= interval && data[j - interval] > temp; j -= interval) {
data[j] = data[j - interval];
}
data[j] = temp;
}
}
}
int main() {
int data[] = {8, 6, 7, 2, 1, 4, 5, 3};
int size = sizeof(data) / sizeof(data[0]);
ShellSort(data, size);
cout << "Sorted Output: \n";
for (int i = 0; i < size; i++)
cout << data[i] << " ";
cout << "\n";
}
出力：
Sorted Output: 1 2 3 4 5 6 7 8
シェルソートの例 Python
入力：
#Shell Sort Example in Python
def ShellSort(data, size):
interval = size // 2
while interval > 0:
for i in range(interval, size):
temp = data[i]
j = i
while j >= interval and data[j - interval] > temp:
data[j] = data[j - interval]
j -= interval
data[j] = temp
interval //= 2
data = [8, 6, 7, 2, 1, 4, 5, 3]
ShellSort(data, len(data))
print('Sorted Output:')
print(data)
出力：
Sorted Output: [1, 2, 3, 4, 5, 6, 7, 8]
シェルソートの応用例
シェル ソートの重要な用途を次に示します。
- シェルソートは、 Linuxカーネル コールスタックを使用しないためです。
- uClibc ライブラリはシェル ソートを使用します。
- bzip2 圧縮プログラムはシェル ソートを使用して超過再帰を停止します。
シェルソートのメリットとデメリット
| Advantages | デメリット |
|---|---|
| スタック呼び出しは必要ありません。 | 巨大な配列サイズでは効率的ではありません。 |
| 簡単な実装。 | 広範囲に広がる要素には非効率的です。 |
| 要素の間隔が狭い場合に効率的です。 |
シェルソートの複雑性分析
シェルソートの時間計算量
シェルソートアルゴリズムの時間計算量は O(n^2) です。その理由は次のとおりです。
最良のシナリオでは、配列が以前に配置されていたときのすべての間隔のテストの合計量は log n に等しくなります。したがって、複雑さは O(n*log n) になります。
最悪の場合のシナリオとして、要素が最も多くの比較を必要とするように配列が構成されていると考えてみましょう。 その後、最後の反復まで、すべての要素の比較や切り替えは行われません。 したがって、最終的な増分に必要な比較の合計は O(n^2) です。
結論として、時間的複雑さは
- 最良の場合の複雑さ: O(n*log n)
- 平均ケース複雑度: O(n*log n)
- 最悪の場合の複雑さ: O(n^2)
シェルソートの実行時間の複雑さは、使用されるギャップ増分シーケンスに大きく依存します。ただし、シェルソートに最適な増分シーケンスはまだわかっていません。
シェルソートの空間計算量
この比較ソートでは、追加の補助スペースは必要ありません。したがって、この種のアルゴリズムの空間計算量は O(1) です。
