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

アルゴリズム分析

挿入ソートでは隣り合う要素で比較、交換が行われます、シェルソートは 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;
  }
}

Python

shellsort_shift() は上記のC言語のコードを Python で実装したものになります。h-ソートの h を表しているのが gap です。insertionsort_swap() は値の交換に一時変数を使用しない実装です。

def shellsort_shift( aList ):
    gap = len(aList) // 2

    while gap > 0:
        for right in range(gap, len(aList)):
            key = aList[right]
            left = right
            while left > 0 and key < aList[left - 1]:
                aList[left] = aList[left - 1]
                left -= 1
            aList[left] = key
        gap //= 2
    return aList

def shellsort_swap( aList ):
    gap = len(aList) // 2

    while gap > 0:
        for right in range(gap, len(aList)):
            left = right
            while left > 0 and aList[left] < aList[left - 1]:
                aList[left - 1], aList[left] = aList[left], aList[left - 1]
                left -= 1
        gap //= 2
    return aList


if __name__ == '__main__':
    from random import shuffle
    l = range(15)
    lcopy = l[:]
    shuffle(l)
    print('Unsorted')
    print l
    assert l != lcopy
    print ('Sorted')
    print shellsort_shift(l)
    assert l == lcopy