データ構造とアルゴリズム-シェルソート

シェルソートは非常に効率的なソートアルゴリズムであり、挿入ソートアルゴリズムに基づいています。このアルゴリズムは、小さい値が右端にあり、左端に移動する必要がある場合に、挿入ソートの場合のように大きなシフトを回避します。

このアルゴリズムは、広く広がっている要素に対して挿入ソートを使用します。最初にそれらをソートし、次に間隔の狭い要素をソートします。この間隔は、interval。この間隔は、クヌースの式に基づいて次のように計算されます。

クヌースの公式

h = h * 3 + 1
where −
   h is interval with initial value 1

このアルゴリズムの平均および最悪の場合の複雑さは、最もよく知られているギャップシーケンスがΟ(n)に依存するため、このアルゴリズムは中規模のデータセットに対して非常に効率的です。ここで、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プログラミング言語でのシェルソートの実装については、ここをクリックしてください。