この記事では、シェルソートアルゴリズムについて説明します。シェル ソートは挿入ソートを一般化したもので、いくつかの位置のギャップで区切られた要素を比較することで挿入ソートの欠点を克服します。
挿入ソートの拡張版であるソートアルゴリズムです。シェル ソートにより、挿入ソートの平均時間の複雑さが改善されました。挿入ソートと同様、比較ベースのインプレースソートアルゴリズムです。シェル ソートは、中規模のデータ セットの場合に効率的です。
挿入ソートでは、要素は一度に 1 位置だけ前に移動できます。要素を遠くの位置に移動するには、多くの移動が必要となり、アルゴリズムの実行時間が増加します。しかし、シェル ソートは、挿入ソートのこの欠点を克服します。遠く離れた要素の移動や交換も可能になります。
このアルゴリズムは、まず互いに遠く離れた要素を並べ替えてから、それらの間のギャップを減らします。このギャップは次のように呼ばれます 間隔。 この間隔は次を使用して計算できます。 クヌースの 以下の式 -
int 文字列 Java
h = h * 3 + 1 where, 'h' is the interval having initial value 1.
では、シェルソートのアルゴリズムを見てみましょう。
アルゴリズム
シェルソートを実現する簡単な手順は次のとおりです。
バイナリツリーとBSTの比較
ShellSort(a, n) // 'a' is the given array, 'n' is the size of array for (interval = n/2; interval > 0; interval /= 2) for ( i = interval; i <n; i +="1)" temp="a[i];" for (j="i;" j>= interval && a[j - interval] > temp; j -= interval) a[j] = a[j - interval]; a[j] = temp; End ShellSort </n;>
シェルソートアルゴリズムの仕組み
ここで、シェルソートアルゴリズムの仕組みを見てみましょう。
シェルのソート アルゴリズムの動作を理解するために、ソートされていない配列を取り上げてみましょう。例を使用すると、シェル ソートを理解しやすくなります。
配列の要素を次のようにします -
シェルソートの元の順序、つまり N/2、N/4、....、1 を間隔として使用します。
最初のループでは、n は 8 (配列のサイズ) に等しいため、要素は 4 の間隔 (n/2 = 4) で配置されます。要素は比較され、順序が正しくない場合は交換されます。
ここで、最初のループでは、0 にある要素が番目位置は 4 の要素と比較されます番目位置。 0の場合番目要素が大きい場合、4 の要素と交換されます番目位置。それ以外の場合は、同じままです。このプロセスは残りの要素に対して続行されます。
間隔 4 では、サブリストは {33, 12}、{31, 17}、{40, 25}、{8, 42} になります。
ここで、すべてのサブリストの値を比較する必要があります。比較後、必要に応じて元の配列でそれらを交換する必要があります。比較して交換すると、更新された配列は次のようになります。
2 番目のループでは、要素は 2 (n/4 = 2) の間隔で配置されます (n = 8)。
ギガバイトとメガバイト
現在、次の間隔をとっています。 2 配列の残りの部分を並べ替えます。間隔を 2 にすると、{12, 25, 33, 40} と {17, 8, 31, 42} の 2 つのサブリストが生成されます。
ここで、再びすべてのサブリストの値を比較する必要があります。比較後、必要に応じて元の配列でそれらを交換する必要があります。比較して交換すると、更新された配列は次のようになります。
C++で優先キュー
3 番目のループでは、要素は 1 (n/8 = 1) の間隔 (n = 8) で配置されます。最後に、値 1 の間隔を使用して残りの配列要素を並べ替えます。このステップでは、シェル ソートは挿入ソートを使用して配列要素をソートします。
これで、配列が昇順に並べ替えられました。
シェルソートの複雑さ
ここで、最良のケース、平均的なケース、最悪のケースにおけるシェル ソートの時間計算量を見てみましょう。シェル ソートの空間の複雑さも見ていきます。
1. 時間計算量
| 場合 | 時間計算量 |
|---|---|
| 最良の場合 | O(n*logn) |
| 平均的なケース | O(n*log(n)2) |
| 最悪の場合 | の上2) |
2. 空間の複雑さ
| 空間の複雑さ | ○(1) |
| 安定した | いいえ |
- シェル ソートの空間計算量は O(1) です。
シェルソートの実装
ここで、さまざまなプログラミング言語での Shell sort のプログラムを見てみましょう。
プログラム： シェルソートを実装するプログラムをC言語で書きます。
#include /* function to implement shellSort */ int shell(int a[], int n) { /* Rearrange the array elements at n/2, n/4, ..., 1 intervals */ for (int interval = n/2; interval > 0; interval /= 2) { for (int i = interval; i <n; i +="1)" { * store a[i] to the variable temp and make ith position empty int j; for (j="i;" j>= interval && a[j - interval] > temp; j -= interval) a[j] = a[j - interval]; // put temp (the original a[i]) in its correct position a[j] = temp; } } return 0; } void printArr(int a[], int n) /* function to print the array elements */ { int i; for (i = 0; i <n; 42 i++) printf('%d ', a[i]); } int main() { a[]="{" 33, 31, 40, 8, 12, 17, 25, }; n="sizeof(a)" sizeof(a[0]); printf('before sorting array elements are -
'); printarr(a, n); shell(a, printf('
after applying shell sort, the return 0; < pre> <p> <strong>Output</strong> </p> <p>After the execution of above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/72/shell-sort-algorithm-7.webp" alt="Shell Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement Shell sort in C++.</p> <pre> #include using namespace std; /* function to implement shellSort */ int shell(int a[], int n) { /* Rearrange the array elements at n/2, n/4, ..., 1 intervals */ for (int interval = n/2; interval > 0; interval /= 2) { for (int i = interval; i <n; i +="1)" { * store a[i] to the variable temp and make ith position empty int j; for (j="i;" j>= interval && a[j - interval] > temp; j -= interval) a[j] = a[j - interval]; // put temp (the original a[i]) in its correct position a[j] = temp; } } return 0; } void printArr(int a[], int n) /* function to print the array elements */ { int i; for (i = 0; i <n; 41 i++) cout< <a[i]<<' '; } int main() { a[]="{" 32, 30, 39, 7, 11, 16, 24, }; n="sizeof(a)" sizeof(a[0]); cout<<'before sorting array elements are -
'; printarr(a, n); shell(a, cout<<'
after applying shell sort, the return 0; < pre> <p> <strong>Output</strong> </p> <p>After the execution of the above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/72/shell-sort-algorithm-8.webp" alt="Shell Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement Shell sort in C#.</p> <pre> using System; class ShellSort { /* function to implement shellSort */ static void shell(int[] a, int n) { /* Rearrange the array elements at n/2, n/4, ..., 1 intervals */ for (int interval = n/2; interval > 0; interval /= 2) { for (int i = interval; i <n; i +="1)" { * store a[i] to the variable temp and make ith position empty int j; for (j="i;" j>= interval && a[j - interval] > temp; j -= interval) a[j] = a[j - interval]; /* put temp (the original a[i]) in its correct position */ a[j] = temp; } } } static void printArr(int[] a, int n) /* function to print the array elements */ { int i; for (i = 0; i <n; 40 i++) console.write(a[i] + ' '); } static void main() { int[] a="{" 31, 29, 38, 6, 10, 15, 23, }; int n="a.Length;" console.write('before sorting array elements are -
'); printarr(a, n); shell(a, console.write('
after applying shell sort, the < pre> <p> <strong>Output</strong> </p> <p>After the execution of the above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/72/shell-sort-algorithm-9.webp" alt="Shell Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement Shell sort in Java.</p> <pre> class ShellSort { /* function to implement shellSort */ static void shell(int a[], int n) { /* Rearrange the array elements at n/2, n/4, ..., 1 intervals */ for (int interval = n/2; interval > 0; interval /= 2) { for (int i = interval; i <n; i +="1)" { * store a[i] to the variable temp and make ith position empty int j; for (j="i;" j>= interval && a[j - interval] > temp; j -= interval) a[j] = a[j - interval]; /* put temp (the original a[i]) in its correct position */ a[j] = temp; } } } static void printArr(int a[], int n) /* function to print the array elements */ { int i; for (i = 0; i <n; 39 i++) system.out.print(a[i] + ' '); } public static void main(string args[]) { int a[]="{" 30, 28, 37, 5, 9, 14, 22, }; n="a.length;" system.out.print('before sorting array elements are -
'); printarr(a, n); shell(a, system.out.print('
after applying shell sort, the < pre> <p> <strong>Output</strong> </p> <p>After the execution of the above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/72/shell-sort-algorithm-10.webp" alt="Shell Sort Algorithm"> <p>So, that's all about the article. Hope the article will be helpful and informative to you.</p> <hr></n;></n;></pre></n;></n;></pre></n;></n;></pre></n;></n;>