読者です 読者をやめる 読者になる 読者になる

kakts-log

programming について調べたことを整理していきます

シェルソートについて

アルゴリズム シェルソート python

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

計算量は以下の通りです。
- 最悪時計算量 アルゴリズムの間隔関数に依存するが、  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だけ離れた要素を比較します。 それによって、ある程度値にばらつきのある配列をソートする際に、並び替え回数が減らせるため処理速度が改善します。

シェルソート分析

一般的にシェルソートは大規模なリストに対しては最適でなく、1000〜10000までの中規模なアルゴリズムにおいて最も効率が良いと言われています。  O(n^2)アルゴリズムのなかでは最も高速となります。

シェルソートの欠点

欠点としては、アルゴリズムが複雑であり、マージソートヒープソートクイックソートと比べたときに効率的でない点があげられます。