Data-structures-algorithms-shell-sort-algorithm
データ構造とアルゴリズム-シェルソート
シェルソートは非常に効率的なソートアルゴリズムであり、挿入ソートアルゴリズムに基づいています。 このアルゴリズムは、より小さい値が右端にあり、左端に移動する必要がある場合、挿入ソートの場合のような大きなシフトを回避します。
このアルゴリズムは、最初にそれらをソートし、次に間隔の狭い要素をソートするために、広範囲に広がるエレメントで挿入ソートを使用します。 この間隔は*間隔*と呼ばれます。 この間隔は、クヌースの式に基づいて計算されます-
クヌースの式
h = h * 3 + 1
where −
h is interval with initial value 1
このアルゴリズムの平均および最悪の複雑さは、最もよく知られているギャップシーケンスに依存するため、このアルゴリズムは中規模のデータセットに対して非常に効率的です。nはアイテムの数です。 そして、最悪の場合のスペースの複雑さはO(n)です。
シェルソートの仕組み
次の例を考えて、シェルソートがどのように機能するかを考えてみましょう。 前の例で使用したのと同じ配列を使用します。 例と理解を容易にするために、4の間隔をとります。 4つの位置の間隔にあるすべての値の仮想サブリストを作成します。 ここで、これらの値は\ {35、14}、\ {33、19}、\ {42、27}および\ {10、44}です
各サブリストの値を比較し、(必要に応じて)元の配列で交換します。 このステップの後、新しい配列は次のようになります-
次に、間隔を1にすると、このギャップは2つのサブリストを生成します-\ {14、27、35、42}、\ {19、10、33、44}
必要に応じて、元の配列の値を比較して交換します。 このステップの後、配列は次のようになります-
最後に、値1の間隔を使用して残りの配列を並べ替えます。 シェルソートは、挿入ソートを使用して配列をソートします。
以下は、段階的な描写です-
残りの配列をソートするために必要なスワップは4つだけであることがわかります。
アルゴリズム
以下は、シェルソートのアルゴリズムです。
Step 1 − Initialize the value of h
Step 2 − Divide the list into smaller sub-list of equal interval h
Step 3 − Sort these sub-lists using insertion sort
Step 3 − Repeat until complete list is sorted
疑似コード
以下は、シェルソートの擬似コードです。
procedure shellSort()
A : array of items
/* calculate interval*/
while interval < A.length/3 do:
interval = interval * 3 + 1
end while
while interval > 0 do:
for outer = interval; outer < A.length; outer ++ do:
/*select value to be inserted*/
valueToInsert = A[outer]
inner = outer;
/*shift element towards right*/
while inner > interval -1 && A[inner - interval] >= valueToInsert do:
A[inner] = A[inner - interval]
inner = inner - interval
end while
/*insert the number at hole position*/
A[inner] = valueToInsert
end for
/* calculate interval*/
interval = (interval -1)/3;
end while
end procedure
Cプログラミング言語でのシェルソートの実装については、リンク:/data_structures_algorithms/shell_sort_program_in_c [ここをクリック]をご覧ください。