はかせのラボ

私の頭の中を書いていく雑記ブログです

プログラミング　今話題のスターリンソートをLINQの拡張メソッドにしてみた

プログラミング C#

あいさつ

どうも、はかせです。
今回は今ちょっと話題になっている
スターリンソートをLINQの拡張メソッドで作ってみた話です。

スターリンソートとは？


昇順になっていないやつを削除粛清することで
計算量O(n)でソートをしてしまうという革命的なソートアルゴリズムです。

LINQで実装してみる

C#だったら既に公式実装があるのですが、
これを改造して
・LINQの拡張メソッドにする
・昇順降順を設定できるようにする
この二つをやってみます。

ではとやかく言う前にコードです。

namespace Expansion
{
    public enum OrderBy
    {
        Asc, Desc
    }
    public static class Expansion
    {
        
        public static IEnumerable<T> StalinSort<T>(this IEnumerable<T> source,OrderBy order = OrderBy.Asc) where T : IComparable<T>
        {
            T previousValue = source.First();
            Func<T,T,bool> conditions = (c1, c2) => Comparer<T>.Default.Compare(c1, c2) < 0;
            if(order == OrderBy.Desc)
            {
                conditions = (c1, c2) => Comparer<T>.Default.Compare(c1, c2) > 0;
            }
            foreach (var currentValue in source)
            {
                if (conditions(currentValue,previousValue)) continue;
                previousValue = currentValue;
                yield return currentValue;
            }
        }
    }
}

やってることは単純で公式実装の判定部分をデリゲートに置き換えて
デリゲートの中身を引数によって切り替えているだけです。

ちなみにデフォルトを昇順にしてるのは私が良く使うツールとかの
並び替えのデフォルトが昇順だからです。

LINQの拡張メソッド化は IEnumerable＜T＞返して
引数にthis IEnumerable＜T＞受け取れば成立します。

それでは使い方と実行結果です。

static void Main(string[] args)
{
    var intArray = new int[] { 10, 2, 21, 98, 1, 85, 6, 48, 55, 963, 85 }; 
    Console.WriteLine("IntArray NotStalinSort");
    foreach (var n in intArray)
    {
        Console.Write(n + "\t");
    }
    Console.WriteLine();
    Console.WriteLine("IntArray StalinSort Asc");
    foreach (var n in intArray.StalinSort())
    {
       Console.Write(n + "\t");
    }
    Console.WriteLine();

    Console.WriteLine("IntArray StalinSort Desc");
    foreach (var n in intArray.StalinSort(OrderBy.Desc))
    {
       Console.Write(n + "\t");
    }
    Console.WriteLine();
}

(値とかは適当です)
f:id:hakase0274:20190804235202p:plain

あとがき

今回は話題のスターリンソートをちょこっと改造してみた話でした。

そんなに難しいことはしていないつもりです。
時間も30分かかってないと思います。
なのでみなさんも落ちてるソースを改造して自分好みにしてはどうでしょうか？

それでは今回はこの辺でノシ