shell sort c with examples
C ++でのシェルソート手法：完全な概要。
シェルソートは、挿入ソートの改善と呼ばれることがよくあります。挿入ソートでは、要素を比較して適切な位置に配置するために1ずつ増加します。
シェルソートでは、リストはいくつかの小さなサブリストに分割してソートされます。リストが連続した要素である必要はありません。代わりに、シェルソート手法は「ギャップ」とも呼ばれる増分iを使用し、それを使用して「i」要素が離れている要素のリストを作成します。
=> 完全なC ++チュートリアルリストについては、こちらをご覧ください。
コンピュータのオペレーティングシステムの名前
学習内容：
一般的なアルゴリズム
シェルソートの一般的なアルゴリズムを以下に示します。
shell_sort（A、N）
ここで、A –ソートするリスト。 N –ギャップサイズ
ギャップサイズ= N、フラグ= 1に設定
gap_size> 1またはflag = 1の場合、繰り返します
ベギン
フラグを設定= 0
ギャップサイズを設定=（gap_size + 1）/ 2
終わり
i = 0からiの場合<(N-gap_size) repeat
ベギン
A (i + gap_size)> A (i)の場合
スワップA (i + gap_size)、A (i)
フラグを設定= 0
終わり
終わり
したがって、上記のアルゴリズムでは、最初に、シェルソートを使用して配列AをソートするためのギャップであるNを設定します。次のステップでは、ギャップを使用して配列をサブ配列に分割します。次に、次のステップで、各サブ配列を並べ替えて、ループの最後に並べ替えられた配列を取得します。
次に、画像表現を使用してシェルソートをよりよく理解するための詳細な例を考えてみましょう。
図
例を使ってシェルソートを説明しましょう。
次の10個の要素の配列について考えてみます。
3のギャップを提供すると、3つの要素が離れている各要素を持つ次のサブリストが作成されます。次に、これら3つのサブリストを並べ替えます。
ソートされたサブリストと、3つのソートされたサブリストを組み合わせた後に得られる結果のリストを以下に示します。
ソートされたサブ配列をマージした後に取得した上記の配列は、ほぼソートされています。これで、このリストに対して挿入ソートを実行し、配列全体をソートできます。この最後のステップは、参考のために以下に示されています。
上記のように、シェルソートを実行し、ソートされたサブリストをマージした後、リストを完全にソートするために必要な移動は3回だけでした。したがって、配列の並べ替えに必要なステップ数を大幅に削減できることがわかります。
サブリストを作成するための増分の選択は、シェルソートのユニークな機能です。
C ++の例
以下のC ++でのシェルソートの実装を見てみましょう。
#include using namespace std; // shellsort implementation int shellSort(int arr(), int N) { for (int gap = N/2; gap > 0; gap /= 2) { for (int i = gap; i = gap && arr(j - gap) > temp; j -= gap) arr(j) = arr(j - gap); arr(j) = temp; } } return 0; } int main() { int arr() = {45,23,53,43,18,24,8,95,101}, i; //Calculate size of array int N = sizeof(arr)/sizeof(arr(0)); cout << 'Array to be sorted:
'; for (int i=0; i 出力：
ソートする配列：
45 23 53 43 18 24 8 95101
シェルソート後の配列：
8 18 23 24 43 45 53 95101
図で使用したものと同じリストを使用しました。最初に2つのサブリストを作成し、次にギャップをさらに狭めることから始めていることがわかります。指定されたギャップに従ってサブリストが作成されたら、各サブリストを並べ替えます。すべてのサブリストがソートされた後、ほぼソートされたリストを取得します。これで、このリストは、ほとんど移動しない基本的な挿入ソートを使用してソートできます。
次に、Java言語を使用してシェルソートを実装しましょう。
Javaの例
// Java class for ShellSort class ShellSort { //function to sort the array using shell sort int sort(int arr()) { int N = arr.length; // Start with a big gap, then narrow the gap for (int gap = N/2; gap > 0; gap /= 2) { //sort sub lists created by applying gap for (int i = gap; i = gap && arr(j - gap) > temp; j -= gap) arr(j) = arr(j - gap); arr(j) = temp; } } return 0; } } class Main{ public static void main(String args()) { int arr() = {45,23,53,43,18,24,8,95,101}; int N = arr.length; System.out.println('Array to be sorted: '); for (int i=0; i 出力：
ソートする配列：
45 23 53 43 18 24 8 95101
シェルソート後の配列：
8 18 23 24 43 45 53 95101
C ++プログラムとJavaプログラムの両方でシェルソートに同じロジックを実装しました。したがって、上記のJavaプログラムで説明したように、最初に配列をサブ配列に分割し、次にそれらをソートして完全にソートされた配列を取得します。
結論
シェルソートは、挿入ソートよりも改善された非常に効率的なアルゴリズムです。
挿入ソートは要素を1つインクリメントすることで機能しますが、シェルソートはパラメータ「gap」を使用して、要素が「ギャップ」離れているサブ配列に配列を分割します。次に、挿入ソートを使用して個々のリストをソートし、完全にソートされた配列を取得できます。
シェルソートは、挿入ソートよりも実行速度が速く、挿入ソートと比較して、配列をソートするための移動が少なくて済みます。今後のチュートリアルでは、データ構造をソートするためのヒープソート手法についてすべて説明します。
=> ゼロからC ++を学ぶには、ここにアクセスしてください。
推奨読書