選択ソート

概要

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

1. 配列の中で最小の要素を探して、先頭の要素と交換する。
2. 未整列の部分に対して、1の処理を繰り返す。

比較の回数はバブルソートと同様に多い部類に入りますが、 要素の交換の回数は常に一定して少ないという特徴があります。 そのため、「比較は簡単だけど、要素の交換は遅い」と言うようなデータ構造に対しては比較的高速になります。

サンプルソース

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