シェルソートについて

シェルソートは前回紹介した挿入ソートの改良版アルゴリズムです。
挿入ソートは一般的に、配列がほとんどソートされた状態で効率的に機能するもので、それ以外の場合では大きくパフォーマンスが落ちるのですが
シェルソートではその欠点を補う仕組みになっています。

計算量は以下の通りです。
- 最悪時計算量アルゴリズムの間隔関数に依存するが、 $O(nlog^2n)$
- 最良時計算量 $O(n)$
- 空間計算量 $O(1)$

アルゴリズムをpythonで書いてみると、以下の通りになります。

import sys

# シェルソート
def shellSort(aList):
    subListCount = len(aList) // 2
    while subListCount > 0:
        for pos in range(subListCount):
            doGapInsertionSort(aList, pos, subListCount)

        print("After increments of size", subListCount);
        print("The list is", aList);

        subListCount = subListCount // 2

# 挿入ソート ギャップあり版
def doGapInsertionSort(aList, startPos, gap):
    for i in range(startPos + gap, len(aList), gap):
        currentVal = aList[i]
        position = i
        while position >= gap and aList[position - gap] > currentVal:
            aList[position] = aList[position - gap]
            position = position - gap

        aList[position] = currentVal

a = [int(a_temp) for a_temp in input().strip().split(' ')]

#シェルソート実行
shellSort(a)
print(a)

シェルソートと挿入ソートの違い

挿入ソートでは、隣接要素間で比較を行い、2つの要素が逆順になっていたら値を交換していく処理になります。
それと違って、シェルソートでは、離れた要素間の比較と交換を実行できるようにし、アルゴリズムの最終ステップまで隣接要素を比較しないようになります。
挿入ソートでは1だけ離れたものを比較し、シェルソートではhだけ離れた要素を比較します。それによって、ある程度値にばらつきのある配列をソートする際に、並び替え回数が減らせるため処理速度が改善します。