シェルソート

概要

シェルソート（Shell sort）は、 挿入ソートを改良した物で、 挿入ソートの「概ねソート済みの配列に対しては高速」という性質を最大限生かすアルゴリズムです。 不安定な内部ソート。

1. 適当な間隔 h を設定して、h 個おきのデータを挿入ソートでソートする。
2. h の間隔を狭めて 1 を繰り返す。

演算量に関しては、理論的に証明するのは非常に難しいけども、 実験的には最良の場合で O(n^1.2) くらいになるらしい。 最悪の場合は挿入ソートなどと同様の O(n²)。

ちなみに、シェルソートの Shell は貝殻とかではなく、人名らしい。

サンプルソース

/// <summary>
/// シェルソート。
/// </summary>
/// <param name="a">対象の配列</param>
public static void ShellSort<T>(T[] a)
  where T : IComparable<T>
{
  int n = a.Length;
  int h;
  for (h = 1; h < n / 9; h = h * 3 + 1) ;
  for (; h > 0; h /= 3)
    for (int i = h; i < n; i++)
      for (int j = i; j >= h && a[j - h].CompareTo(a[j]) > 0; j -= h)
        Swap(ref a[j], ref a[j - h]);
}