本記事は、ソフトバンクパブリッシングから発行されている「定本 Cプログラマのためのアルゴリズムとデータ構造 (SOFTBANK BOOKS)」を参考にPythonでアルゴリズムとデータ構造について学習していきます。
今回は、かつて最高速な整列アルゴリズムであったシェルソート(Shell Sort)について学んでいきます。
シェルソートとは
シェルソート(Shell Sort)とは、1959年にD.Shellによって考案された整列アルゴリズムで、クイックソートが発見されるまでは最も高速な整列アルゴリズムでした。
シェルソートは前回学んだ挿入ソートをベースとして考えられています。
挿入ソートでは、ある程度整列済みのデータに関してその能力が発揮できるという特徴がありました。
この特徴を生かして、予め整列度を高めるための前処理を行うのがシェルソートになります。
なお、シェルソートは安定な整列アルゴリズム(データの位置関係が保存される)ではありません。
h-ソートとは
シェルソートでは、予め整列度を高めるための前処理として、一定の距離を置いた二つの値を比較し、交換することで整列度を高めていきます。
この一定の距離()ずつ離れた要素を整列することを-ソートと言い、ずつ離れた要素同士が互いに整列済みであることを-ソート済みと言います。
以下では4つずつ離れたデータ(4-ソート)を整列させます。
以下は4-ソート後のデータになります。
その後、を小さくしていき、2-ソート、1-ソートと実行して、最終的に整列が完了します。
hの選択方法
上記の例ではという数列を用いて、を減少させることで整列が完了します。
この-ソートを行うためにどのような数列を使うかで性能が変わってきます。
書籍では、「3倍して1を加える」という方法が、計算量的に良好であることが挙げられています。
シェルソートの計算量
シェルソートでは最終的には挿入ソートを呼び出しますが、その前処理としてh-ソートをします。
挿入ソートの計算量は、ほぼデータが整列済みであれば、そうでなければでした。
例えば100個のデータを50ソートさせる場合、整列させる組(2つのデータ)を()とすると、その計算量はとなり、データ数をとすると、となりますが、はよりも十分に小さいため、実際はの計算量になります。
また最終的に挿入ソートを呼び出しますが、この時にはかなり整列度が高いため、よりも小さいオーダーで実行が可能となります。
なお、上記の「3倍して1を加える」という数列を使用すると、くらいの計算量になることが分かっています。
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))
動作確認
それでは上記で作成したスクリプトを実行してみます。
事前に1~20,000までの値からランダムに20,000個生成したリストをpickleデータとして保存しておき、これをロードします。
自環境で実行した結果を以下にまとめます。
アルゴリズム名 | 所要時間(秒) |
---|---|
Python 組込みメソッド(sort()) | 0.015 |
Bubble Sort | 72.979 |
Selection Sort | 17.747 |
Insertion Sort | 41.236 |
Shell Sort | 0.253 |
上記の単純な整列アルゴリズムに比べれば恐ろしいほど高速になりました。