シェルソート [Shell Sort]

シェルソートは挿入ソートが改良された整列アルゴリズムです。リストにおいてあらかじめ離れている要素を交換しておき、最終的に挿入ソートを実行します。
挿入ソートが整列済みのリストに強いことを利用した効率の良い整列アルゴリズムです。

アルゴリズム分析

挿入ソートでは隣り合う要素で比較、交換が行われます、シェルソートは h ずつ離れた要素を比較/交換します。

h 離れた要素を整列する処理を h-ソート と言います。h-ソートの整列ロジックには挿入ソートが用いられます。

シェルソートでは h-ソートの h の数を小さくしてゆくことで最終的に単純な挿入ソート(h=1)になります。挿入ソートになった頃には「ほぼ整列している」状態ができあがっているので挿入ソートのメリットを活かした整列が行えるのです。

特徴

h-ソートの手間(計算量)があっても、結果的に少ない計算量で完了するのがシェルソートの特徴です。

サンプルコード

C言語

h-ソートの h を表しているのが increment です。increment は 4, 2, 1, 0 と減少します(0 で while ループ終了)。

void shellSort(int numbers[], int array_size)
{
  int i, j, increment, temp;

  increment = 4;
  while (increment > 0)
  {
    for (i=0; i < array_size; i++)
    {
      j = i;
      temp = numbers[i];
      while ((j >= increment) && (numbers[j-increment] > temp))
      {
        numbers[j] = numbers[j - increment];
        j = j - increment;
      }
      numbers[j] = temp;
    }
    if (increment/2 != 0)
      increment = increment/2;
    else if (increment == 1)
      increment = 0;
    else
      increment = 1;
  }
}