スターリンソートをLINQと拡張メソッドで実装

概要

これを見て何となく自分もスターリンソートを書いてみました。

また、公式でC#のコードが掲載されていましたが、拡張メソッドやLINQ、ジェネリックなどが全然使われていない！
これはC#信者として見過ごす訳にはいきません。(過激派)
(2019/08/04追記)
他の有志のプルリクによって、IEnumerable<T>を返す実装になりました。
ただ、現時点のソースコードにおいても下記のような実装はされていません。

• 拡張メソッドで呼べるようにする
• 昇順降順を決める
• 比較方法をカスタマイズする
• ソート済みのコレクションを更にソートする

ということで、上記の機能を実装してみます。
C# 8.0で動作を確認しています。コンパイルが通らない場合はusing変数辺りを修正すれば動作すると思います。

拡張クラス

using System;
using System.Linq;
using System.Collections.Generic;

namespace StalinSort
{
    static class StalinSortExtension
    {
        public static IOrderedEnumerable<TSource> StalinSortBy<TSource, TKey>(
            this IEnumerable<TSource> source,
            Func<TSource, TKey> keySelector)
        {
            return source
                .StalinSort(keySelector, null, false)
                .OrderBy(keySelector);
        }

        public static IOrderedEnumerable<TSource> StalinSortBy<TSource, TKey>(
            this IEnumerable<TSource> source,
            Func<TSource, TKey> keySelector,
            IComparer<TKey> comparer)
        {
            return source
                .StalinSort(keySelector, comparer, false)
                .OrderBy(keySelector, comparer);
        }

        public static IOrderedEnumerable<TSource> StalinSortByDescending<TSource, TKey>(
            this IEnumerable<TSource> source,
            Func<TSource, TKey> keySelector)
        {
            return source
                .StalinSort(keySelector, null, true)
                .OrderByDescending(keySelector);
        }

        public static IOrderedEnumerable<TSource> StalinSortByDescending<TSource, TKey>(
            this IEnumerable<TSource> source,
            Func<TSource, TKey> keySelector,
            IComparer<TKey> comparer)
        {
            return source
                .StalinSort(keySelector, comparer, true)
                .OrderByDescending(keySelector, comparer);
        }

        private static IEnumerable<TSource> StalinSort<TSource, TKey>(
            this IEnumerable<TSource> source,
            Func<TSource, TKey> keySelector,
            IComparer<TKey> comparer,
            bool descending)
        {
            using var iterator = source.GetEnumerator();
            if (iterator.MoveNext())
            {
                var c = comparer ?? Comparer<TKey>.Default;
                TKey last = keySelector(iterator.Current);
                yield return iterator.Current;
                while (iterator.MoveNext())
                {
                    TKey current = keySelector(iterator.Current);
                    bool condition = descending ? c.Compare(last, current) >= 0 : c.Compare(last, current) <= 0;
                    if (condition)
                    {
                        last = current;
                        yield return iterator.Current;
                    }
                }
            }
        }
    }
}

実行サンプル

using System;
using System.Linq;
using System.Collections.Generic;
using StalinSort;

namespace asobi
{
    public class Program
    {
        public static void Main()
        {
            var list = new List<int>() { 6, 8, 5, 9, 11, 12, 4, 2, 7, 9 };
            foreach (var e in list.StalinSortBy(x => x))
            {
                Console.WriteLine(e);
            }
            /* 
             * output:
             * 6
             * 8
             * 9
             * 11
             * 12
             */

            var fruits = new List<Fruit>(){
                new Fruit{ Name = "オレンジ", Price = 80 },
                new Fruit{ Name = "ピーチ", Price = 150 },
                new Fruit{ Name = "バナナ", Price = 50 },
                new Fruit{ Name = "グレープ", Price = 250 },
                new Fruit{ Name = "ストロベリー", Price = 20 },
                new Fruit{ Name = "ウォーターメロン", Price = 1200 },
                new Fruit{ Name = "メロン", Price = 2000 },
            };

            foreach (var e in fruits.StalinSortBy(x => x.Name.Length).ThenByDescending(x => x.Price))
            {
                Console.WriteLine($"Name:{e.Name} Price:{e.Price}");
            }
            /*
             *output:
             *Name:グレープ Price:250
             *Name:オレンジ Price:80
             *Name:ストロベリー Price:20
             *Name:ウォーターメロン Price:1200
             */
        }
    }

    public class Fruit{
        public string Name;
        public int Price;
    }
}

要点

• 現在進行形で最大値の要素(last)と要素(current)を比較
• IComparerを使ってその型(TKey)特有の比較ができる
• 見ての通り遅延評価を行っているため、sourceの順序が崩れる心配はない
• 仕組みはOrderByの内部実装とある程度は似せているつもり
• ThenByによる並び変えをできるようにするためIOrderedEnumerable<TSource>を返す(ただ、メソッド内部でOrderByを返したのはかなりズルをしたと思います)

余談

公式のリポジトリに無事マージされました。
https://github.com/gustavo-depaula/stalin-sort/tree/master/c%23/stalin-sort-with-extension