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

アルゴリズム分析

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

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

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

図解

シェルソートの図解

シェルソートのイメージを動画でご覧下さい。人が踊っていますが、ちゃんとシェルソートの動きを表現していますのでご心配なく。音が出ます。

特徴

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

しかしながら、 h をどうやって決定するか(減らしていくのか)によって性能が変わります。下記のサンプルコードでは初期の h を決定したあとは次の h は h / 2 として減少させていますが最終的に h が 1 になるのであれば任意の数を選ぶことができます。興味がある方は h を実験したページ「シェルソートと間隔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 >= gap and key < aList[left - gap]:
                aList[left] = aList[left - gap]
                left -= gap
            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 >=gap and aList[left] < aList[left - gap]:
                aList[left - gap], aList[left] = aList[left], aList[left - gap]
                left -= gap
        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

シェルソートのデモンストレーション プログラム: shell-sort.py

基本情報技術者試験 最速 合格講座

基本情報技術者試験の合格水準の知識を身に着けるオンライン学習コンテンツ

詳しく見る icon