Engineering Note

プログラミングなどの技術的なメモ

シェルソート (Pythonによるアルゴリズムとデータ構造)

shell sort

本記事は、ソフトバンクパブリッシングから発行されている「定本 Cプログラマのためのアルゴリズムとデータ構造 (SOFTBANK BOOKS)」を参考にPythonアルゴリズムとデータ構造について学習していきます。

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

 

 

シェルソートとは

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

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

 

 

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

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

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

 

h-ソートとは

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

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

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

 

fig1. 4-ソート前

fig1. 4-ソート前



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

 

fig2. 4-ソート後

fig2. 4-ソート後

 

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

 

hの選択方法

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

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

 

シェルソートの計算量

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

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

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

 

動作確認

それでは上記で作成したスクリプトを実行してみます。

事前に1~20,000までの値からランダムに20,000個生成したリストをpickleデータとして保存しておき、これをロードします。

自環境で実行した結果を以下にまとめます。

 

データ20,000個を整列した結果一覧
アルゴリズム 所要時間(秒)
Python 組込みメソッド(sort()) 0.015
Bubble Sort 72.979
Selection Sort 17.747
Insertion Sort 41.236
Shell Sort 0.253

 

上記の単純な整列アルゴリズムに比べれば恐ろしいほど高速になりました。

 

参考書籍

定本 Cプログラマのためのアルゴリズムとデータ構造 (SOFTBANK BOOKS)