スリープソートとは

海外掲示板4chanのユーザーにより発表された究極のソートアルゴリズム。
具体的な手順は以下のように超シンプルなもの。

配列から値を読み込み、その値だけの時間スリープする
スリープし終わったらその値を出力する

これを配列の全ての値に対して並列処理してやると、値の小さい方から順に出力される。
比較回数0回、計算量ほぼ0という驚愕の事実に加え、安定ソートであるという優れもの。
（実行時間とメモリに目をつぶれば）

実装してみた

自分のようなひよっこ入門プログラマーにはちょうどいい練習だと思ったので、n番煎じを気にせずやってみた。

    public static class Extensions
    {
        public static IEnumerable<T> SleepSort<T>(this IEnumerable<T> source, Func<T, int> selector)
        {
            var list = new List<T>();
            var sync = new Object();
            var tasks = source.Select(async item =>
            {
                //System.Threading.Thread.Sleep(100); //これをつけると安定ソートとなる
                await Task.Delay(TimeSpan.FromSeconds(selector(item)));
                lock (sync) { list.Add(item); }
            }).ToArray();
            Task.WaitAll(tasks);
            return list;
        }

        public static IEnumerable<int> SleepSort(this IEnumerable<int> source)
        {
            return SleepSort(source, i => i);
        }
    }

LINQっぽくIEnumerable<T>の拡張メソッドに。また、引数にセレクタを使うことで汎用性を高めておく。（そのため、普通のint配列のソートを後でオーバーロードした）

実行

実行例

        static void Main(string[] args)
        {
            var list = new[] { "Alice", "Bob", "Cate", "David", "Eve" };
            foreach (var item in list.SleepSort(s => s.Length))
            {
                Console.WriteLine(item);
            }

            Console.ReadKey();
            return;
        }

結果

Bob
Eve
Cate
David
Alice

どうもC#で並列処理すると各タスクの実行順序がまちまちで、安定ソートにならない模様。
どうしても安定させたい場合は、Thread.Sleepを用いて各タスクの実行開始をわずかにずらすことで解決する。

まとめ

わかってはいたが、実行に時間がかかりすぎる。
実はこれが初めての並列処理で、自分にとってはとても素晴らしい練習問題になったと思う。
同じくらいの入門者の方は是非とも挑戦してほしい。

C#でスリープソート書きました

スリープソートとは

実装してみた

実行

まとめ