https://engineeringnote.hateblo.jp/entry/python/algorithm-and-data-structures/shell

本記事は、ソフトバンクパブリッシングから発行されている「」を参考にPythonでアルゴリズムとデータ構造について学習していきます。

今回は、かつて最高速な整列アルゴリズムであったシェルソート（Shell Sort）について学んでいきます。

シェルソートとは

シェルソート（Shell Sort）とは、1959年にD.Shellによって考案された整列アルゴリズムで、クイックソートが発見されるまでは最も高速な整列アルゴリズムでした。

シェルソートは前回学んだ挿入ソートをベースとして考えられています。

挿入ソートでは、ある程度整列済みのデータに関してその能力が発揮できるという特徴がありました。

この特徴を生かして、予め整列度を高めるための前処理を行うのがシェルソートになります。

なお、シェルソートは安定な整列アルゴリズム（データの位置関係が保存される）ではありません。

h-ソートとは

シェルソートでは、予め整列度を高めるための前処理として、一定の距離を置いた二つの値を比較し、交換することで整列度を高めていきます。

この一定の距離（ $h$ ）ずつ離れた要素を整列することを $h$ -ソートと言い、 $h$ ずつ離れた要素同士が互いに整列済みであることを $h$ -ソート済みと言います。

以下では4つずつ離れたデータ（4-ソート）を整列させます。

以下は4-ソート後のデータになります。

その後、 $h$ を小さくしていき、2-ソート、1-ソートと実行して、最終的に整列が完了します。

hの選択方法

上記の例では $h=4, 2, 1$ という数列を用いて、 $h$ を減少させることで整列が完了します。
この $h$ -ソートを行うためにどのような数列を使うかで性能が変わってきます。

書籍では、「3倍して1を加える」という方法が、計算量的に良好であることが挙げられています。

シェルソートの計算量

シェルソートでは最終的には挿入ソートを呼び出しますが、その前処理としてh-ソートをします。

挿入ソートの計算量は、ほぼデータが整列済みであれば $O(n)$ 、そうでなければ $O(n^2)$ でした。

例えば100個のデータを50ソートさせる場合、整列させる組（2つのデータ）を $i$ （ $i=2$ ）とすると、その計算量は $O(i^2)$ となり、データ数を $n$ とすると、 $\frac{n}{2} \cdot O(i^2)=O(n) \cdot (i^2)$ となりますが、 $i$ は $n$ よりも十分に小さいため、実際は $O(n)$ の計算量になります。

また最終的に挿入ソートを呼び出しますが、この時にはかなり整列度が高いため、 $O(n^2)$ よりも小さいオーダーで実行が可能となります。

なお、上記の「3倍して1を加える」という数列を使用すると、 $O(n^{1.25})$ くらいの計算量になることが分かっています。

Pythonでシェルソートを実装してみる

それでは、Pythonでシェルソートを実装してみます。

# shell_sort.py
import time
import pickle

def shell_sort(lst):
    print("00:",lst)
    print()
    length = len(lst)
    h = 1
    while h < length / 9:
        h = h * 3 + 1
    while h > 0:
        for i in range(h, length):
            j = i
            while j >= h and lst[j-h] > lst[j]:
                tmp = lst[j]
                lst[j] = lst[j-h]
                lst[j-h] = tmp
                j -= h
        print("{:02}: {}".format(i+1, lst))
        h = int(h / 3)


with open('sample_data.pkl', 'rb') as f:
    lst = pickle.load(f)

start = time.time()
lst = [20,6,55,74,3,45,13,87,46,30]
shell_sort(lst)
print("elapsed {} sec".format(time.time() - start))