挿入ソート

概要

挿入ソート（insertion sort）は、 以下のような手順でソートを行うアルゴリズムです。 安定な内部ソート。

1. ソート済みの配列に対して要素を1つ挿入することを考える。
   • 元の配列の末尾に新しい要素を付け加える。
   • 配列の後ろの要素から見ていって、新しい要素よりも値が大きければ、新しい要素と順序を交換していく。
   • 順序交換が必要なくなるところまで進めれば、結果もソート済みの配列になる。
2. 1の処理を、前2つの要素だけ、次は3つ、その次は4つ・・・と繰り返す。

人間が手作業で物を並び替えるのにもっともなじみやすいアルゴリズムだと言われています。 また、シンプルでかつ O(n²) のソートの中では高速な部類に入るので、 非常によく使われます。

概ねソート済みの配列に対しては高速ですが、 逆順に並んだ配列に対してはかなり低速になります。 「概ねソート済みのものに対して高速」という性質のため、 他のソートアルゴリズム（特にクイックソート）で大まかにソートして、 最後は挿入ソートを行うという使い方をされたりします。

サンプルソース

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