【C#】選択ソートを実装してみる

はじめに

今回は選択ソートを実装していきたいと思います。
ja.wikipedia.org

このアルゴリズムは実装は簡単だけど性能がいいといったソートアルゴリズムで、バブルソートと似た系統のものです。

早速みていきましょう。

選択ソート

こちらの動画がすごい分かりやすかったです。
www.youtube.com

実装

public static class SelectionSort<T> where T : IComparable<T>
{
    /// <summary>
    /// 選択ソート
    /// </summary>
    public static T[] Excuse(IEnumerable<T> items)
    {
        var nums = items.ToArray();
        var n = nums.Length;

        for (int i = 0; i < n; i++)
        {
            int min = i;
            for (int j = i + 1; j < n; j++)
                if (nums[min].CompareTo(nums[j]) > 0) min = j;

            Swap(ref nums[i], ref nums[min]);
        }

        return nums;
    }

    private static void Swap(ref T a, ref T b)
    {
        var tmp = a;
        a = b;
        b = tmp;
    }
}

テスト

使い方はこんな感じ。

static void Main(string[] args)
{
    var a = new int[] { 170, 45, 75, 90, 2, 24, 802, 66 };

    foreach (var item in SelectionSort<int>.Excuse(a))
        Console.WriteLine(item);       // 2, 24, 45, 66, 75, 90, 170, 802
}

考察

比較回数は n-1 + n-2 + ... + 1であるので(2重ループの箇所)、o(n(n-1) / 2)となります。

よって最悪計算量はo(n^2)です。