algorithm
シェルソート

シェルの基本情報のソート

シェルソートは、減少インクリメントソートとも呼ばれ、発明者ドナルドの名前を冠した最も古いソートアルゴリズムの1つです。 L. Shell （1959）。理解しやすく、実装が簡単です。しかし、複雑さの分析はもう少し洗練されています。

シェルソートの考え方は次のとおりです。

1. データ配列を2次元配列に配置する
2. 配列の列をソートする

シェルソートは挿入のソートを改善します。これは、離れた要素を比較し、離れた要素を比較し、最後に隣接する要素を比較することから始まります（事実上挿入の並べ替え）。

その効果は、データシーケンスが部分的にソートされていることです。上記のプロセスが繰り返されますが、その都度、より狭いアレイ、すなわちより少ない数の列を用いて繰り返される。最後のステップでは、配列は1つの列のみで構成されます。

シェルソートの例：

シェルソートの疑似コード：

input
foreach element in input
{
    for(i = gap; i < n; i++)
    {
        temp = a[i]
        for (j = i; j >= gap and a[j - gap] > temp; j -= gap)
        {
            a[j] = a[j - gap]
        }
        a[j] = temp
    }
}

補助空間： O(n) total, O(1) auxiliary
時間の複雑さ： O(nlogn)

C＃の実装

public class ShellSort
{
    static void SortShell(int[] input, int n)
    {
        var inc = 3;
        while (inc > 0)
        {
            int i;
            for (i = 0; i < n; i++)
            {
                var j = i;
                var temp = input[i];
                while ((j >= inc) && (input[j - inc] > temp))
                {
                    input[j] = input[j - inc];
                    j = j - inc;
                }
                input[j] = temp;
            }
            if (inc / 2 != 0)
                inc = inc / 2;
            else if (inc == 1)
                inc = 0;
            else
                inc = 1;
        }
    }

    public static int[] Main(int[] input)
    {
        SortShell(input, input.Length);
        return input;
    }
}