シェルソートとは

シェルソートは、挿入ソートを改良したソートアルゴリズムです。挿入ソートの概ねソート済のデータに対して高速に動作する特性を活かすアルゴリズムになっています。

間隔の離れた要素同士をソートでし、段々と間隔を小さくして、最終的には隣り合った要素でソートします。つまり挿入ソートをそのまま行うより、間隔をあけてざっくりとソートしてから挿入ソートを行うほうが、挿入ソートの特性によって高速に処理させることができるのです。

シェルソートは 不安定 な 内部 ソートです。正確な計算量を求めるのは難しいようですが、平均は O(n1.25) くらいになるようです。ただし間隔 h のとり方が大きく影響します。

シェルソート の "シェル" はこのアルゴリズムの発案者 ドナルド・シェル に由来します。

シェルソートのシミュレーション

背景色が黄色のタイミングで比較が実行されています。緑色はソート済(確定ではない)の部分です。ここにデータを挿入します。ソート済のデータは水色になります。間隔 h を 4, 3, 1 の順でソートしています。

アルゴリズムの解説

まずは、適当な間隔 h で 挿入ソートします。h を小さくしながら挿入ソートを繰り返します。最終的に h=1 つまり 通常の挿入ソートを実行しソート完了です。

間隔 h の決め方

このアルゴリズムの重要なのポイントは、間隔 h の決め方です。当然この h の決め方が適当だと、通常の挿入ソートより処理時間がかかってしまうかもしれません。例えば、8, 4, 2, 1 つまり、hi + 1 = 2hiで間隔を決めるのはよくない例です。なぜなら同じ要素が何度も挿入されることになるからです。間隔 h はできるだけ多くの要素がざっくりとソートされる方が良いようです。

間隔 h は、 hi + 1 = 3hi + 1 を満たす h を大きい値から順に採用すると、平均計算量 O(n1.25) が得られるようです。

サンプルコード

C#

public static void ShellSort<T>(T[] array) where T : IComparable<T>
{
    int n = array.Length;
    int h = 0;
    while (h <= n / 9) h = 3 * h + 1;

    // 3h + 1 で間隔を決める
    for (; h > 0; h /= 3)
    {
        // 間隔hで挿入ソート
        // 最終的に通常の挿入ソート(h=1)が実行されて完了
        for (int i = h; i < n; i++)
        {
            var tmp = array[i];
            if (array[i - h].CompareTo(tmp) > 0)
            {
                int j = i;
                do
                {
                    array[j] = array[j - h];
                    j -= h;
                } while (j >= h && array[j - h].CompareTo(tmp) > 0);
                array[j] = tmp;
            }
        }
    }
}

Python

def shell_sort(array):
    n = len(array)
    h = 0

    # 3h + 1 間隔
    while h <= n/9 : h = 3*h + 1
    while h > 0:
        # print("while h =", h)
        # 間隔hで挿入ソート, 最終的に挿入ソート
        for i in range(h, n):
            tmp = array[i] # 挿入する値を退避
            if tmp < array[i-h]: # 挿入する必要があるか
                j = i # 挿入する位置
                while True:
                    array[j] = array[j-h] # h後ろにずらす
                    j -= h
                    if j < h or tmp >= array[j-h]:
                        break
                array[j] = tmp # 空いた位置に退避していた値を挿入
                # print(array)
        h = int(h/3)