シェルソート [Shell Sort]
シェルソートは挿入ソートが改良された整列アルゴリズムです。リストにおいてあらかじめ離れている要素を交換しておき、最終的に挿入ソートを実行します。
挿入ソートが整列済みのリストに強いことを利用した効率の良い整列アルゴリズムです。
アルゴリズム分析
挿入ソートでは隣り合う要素で比較、交換が行われます、シェルソートは 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
