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

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

このアルゴリズムは、最初にそれらをソートし、次に間隔の狭い要素をソートするために、広範囲に広がるエレメントで挿入ソートを使用します。この間隔は*間隔*と呼ばれます。この間隔は、クヌースの式に基づいて計算されます-

クヌースの式

h = h * 3 &plus; 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 [ここをクリック]をご覧ください。

Data-structures-algorithms-shell-sort-algorithm

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

クヌースの式

シェルソートの仕組み

アルゴリズム

疑似コード

目次