C#でバケットソートを実装する

# バケットソートとは
[Wikipedia](https://ja.wikipedia.org/wiki/%E3%83%90%E3%82%B1%E3%83%83%E3%83%88%E3%82%BD%E3%83%BC%E3%83%88)を参照してください。簡単に言うと、値の取りうる範囲が決まっている場合に高速なソートを実現するものです。

# さっそく実装
とりあえず、値の取りうる範囲は与えられるものとします。

```BucketSort.cs
using System;
using System.Collections.Generic;
using System.Linq;

class Program {
    static void Main()
    {
        var rand = new Random();

        var source = new List<int>();
        for (var i = 0; i < 10000; ++i) {
            source.Add(rand.Next(100));
        }

        foreach (var v in BucketSort(source, v => v, Enumerable.Range(0, 100))) {
            Console.WriteLine(v);
        }
    }

    public static IEnumerable<TSource> BucketSort<TSource, TKey>(IEnumerable<TSource> source, Func<TSource, TKey> keySelector, IEnumerable<TKey> keyDomain)
    {
        var buckets = keyDomain.ToDictionary(k => k, _ => new List<TSource>());

        foreach (var v in source) {
            var key = keySelector(v);
            buckets[key].Add(v);
        }

        return buckets.SelectMany(p => p.Value);
    }
}
```
keySelectorはOrderByなどと同じでソートのキーを選択するためのものです。keyDomainが取りうる値の範囲で、0と10しかとらない場合などはnew[] { 0, 10 }とか渡しても大丈夫です。
以上、非常に簡単に実装できました。

# メソッドチェーンで使いたい
と、それで終わるのであればわざわざ記事を作ったりしないですよね。
C#で使うならLINQなんかに絡めて使いたいわけです。上の実装を拡張メソッドにしてしまえば「ほぼ」完了です。ええ。「ほぼ」です。

```
// BucketSortを拡張メソッドにしたとしたら
var source = new List<int>();
for (var i = 0; i < 10000; ++i) {
    source.Add(rand.Next(10000));
}
// LINQで使える
source.Where(v => v < 100)
      .BucketSort(v => v, Enumerable.Range(0, 100))
      .Select(v => v * 2);
```

# お気づきだろうか……
BucketSortの後に別のキーでソートしたい場合を考えてみましょう。

```
var source = new List<Tuple<int, int>>();
for (var i = 0; i < 10000; ++i) {
    source.Add(Tuple.Create(rand.Next(100), rand.Next(100)));
}
var sorted = source
    .BucketSort(v => v.Item1, Enumerable.Range(0, 100))
    .BucketSort(v => v.Item2, Enumerable.Range(0, 100));

foreach (var v in sorted) Console.WriteLine(v); // ???
```

Item1をキーにしてソートした後にItem2でソートするため、やりたい順番とは逆になります。そのためにLINQにはThenByがあります。というわけで、ThenByのような処理も実装しましょう。

# 完成版ソース
[OrderedEnumerable](https://referencesource.microsoft.com/#System.Core/System/Linq/Enumerable.cs,ffb8de6aefac77cc,references)のソースを参考に実装しました。

```BucketSortedEnumerable.cs
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;

public interface IBucketComparer<TKey> : IComparer<TKey> {

    IEnumerable<TKey> KeyDomain { get; }

}

internal class BucketComparer<TKey> : IBucketComparer<TKey> {

    internal IEnumerable<TKey> keyDomain;

    internal BucketComparer(IEnumerable<TKey> keyDomain)
    {
        this.keyDomain = keyDomain;
    }

    public IEnumerable<TKey> KeyDomain { get { return keyDomain; } }

    public int Compare(TKey lhs, TKey rhs)
    {
        throw new NotSupportedException();
    }

}

internal abstract class BucketSortedEnumerable<TSource> : IOrderedEnumerable<TSource> {

    internal IEnumerable<TSource> source;

    internal abstract EnumerableSorter<TSource> GetEnumerableSorter(EnumerableSorter<TSource> next);

    IOrderedEnumerable<TSource> IOrderedEnumerable<TSource>.CreateOrderedEnumerable<TKey>(Func<TSource, TKey> keySelector, IComparer<TKey> comparer, bool descending)
    {
        var result = new BucketSortedEnumerable<TSource, TKey>(source, keySelector, comparer, descending);
        result.parent = this;
        return result;
    }

    public IEnumerator<TSource> GetEnumerator()
    {
        return GetEnumerableSorter(null).Sort(source).GetEnumerator();
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }

}

internal class BucketSortedEnumerable<TSource, TKey> : BucketSortedEnumerable<TSource> {

    internal BucketSortedEnumerable<TSource> parent;
    internal Func<TSource, TKey> keySelector;
    internal IComparer<TKey> comparer;
    internal bool descending;

    internal BucketSortedEnumerable(IEnumerable<TSource> source, Func<TSource, TKey> keySelector, IComparer<TKey> comparer, bool descending)
    {
        if (source == null) throw new ArgumentNullException("source");
        if (keySelector == null) throw new ArgumentNullException("keySelector");

        this.source = source;
        this.parent = null;
        this.keySelector = keySelector;
        this.comparer = comparer != null ? comparer : Comparer<TKey>.Default;
        this.descending = descending;
    }

    internal override EnumerableSorter<TSource> GetEnumerableSorter(EnumerableSorter<TSource> next)
    {
        var bucketComparer = comparer as IBucketComparer<TKey>;

        var sorter = (bucketComparer != null) ?
            (EnumerableSorter<TSource>)new BucketSorter<TSource, TKey>(keySelector, bucketComparer, descending, next) :
            new DefaultSorter<TSource, TKey>(keySelector, comparer, descending, next);

        if (parent != null) sorter = parent.GetEnumerableSorter(sorter);

        return sorter;
    }

}

internal abstract class EnumerableSorter<TSource> {

    internal EnumerableSorter<TSource> next;
    internal bool descending;

    internal abstract IEnumerable<TSource> Sort(IEnumerable<TSource> source);

}

internal class DefaultSorter<TSource, TKey> : EnumerableSorter<TSource> {

    private Func<TSource, TKey> keySelector;
    private IComparer<TKey> comparer;

    internal DefaultSorter(Func<TSource, TKey> keySelector, IComparer<TKey> comparer, bool descending, EnumerableSorter<TSource> next)
    {
        this.keySelector = keySelector;
        this.comparer = comparer;
        this.descending = descending;
        this.next = next;
    }

    internal override IEnumerable<TSource> Sort(IEnumerable<TSource> source)
    {
        source = (descending) ? source.OrderByDescending(keySelector, comparer) : source.OrderBy(keySelector, comparer);
        if (next != null) source = next.Sort(source);
        return source;
    }

}

internal class BucketSorter<TSource, TKey> : EnumerableSorter<TSource> {

    private Func<TSource, TKey> keySelector;
    private IBucketComparer<TKey> comparer;

    internal BucketSorter(Func<TSource, TKey> keySelector, IBucketComparer<TKey> comparer, bool descending, EnumerableSorter<TSource> next)
    {
        this.keySelector = keySelector;
        this.comparer = comparer;
        this.next = next;
        this.descending = descending;
    }

    internal override IEnumerable<TSource> Sort(IEnumerable<TSource> source)
    {
        var keyDomain = comparer.KeyDomain;
        if (keyDomain == null) {
            keyDomain = source.Select(keySelector).Distinct().OrderBy(v => v, comparer);
        }

        var buckets = (descending ? keyDomain.Reverse() : keyDomain).ToDictionary(k => k, _ => new List<TSource>());

        foreach (var v in source) {
            var key = keySelector(v);
            buckets[key].Add(v);
        }

        return buckets.SelectMany(p => (next != null) ? next.Sort(p.Value) : p.Value);
    }

}

public static class Extension {

    public static IOrderedEnumerable<TSource> OrderWithDomainBy<TSource, TKey>(this IEnumerable<TSource> source, Func<TSource, TKey> keySelector, IEnumerable<TKey> keyDomain)
    {
        return new BucketSortedEnumerable<TSource, TKey>(source, keySelector, new BucketComparer<TKey>(keyDomain), false);
    }

    public static IOrderedEnumerable<TSource> OrderWithDomainBy<TSource, TKey>(this IEnumerable<TSource> source, Func<TSource, TKey> keySelector, IBucketComparer<TKey> comparer)
    {
        return new BucketSortedEnumerable<TSource, TKey>(source, keySelector, comparer, false);
    }

    public static IOrderedEnumerable<TSource> OrderWithReversedDomainBy<TSource, TKey>(this IEnumerable<TSource> source, Func<TSource, TKey> keySelector, IEnumerable<TKey> keyDomain)
    {
        return new BucketSortedEnumerable<TSource, TKey>(source, keySelector, new BucketComparer<TKey>(keyDomain), true);
    }

    public static IOrderedEnumerable<TSource> OrderWithReversedDomainBy<TSource, TKey>(this IEnumerable<TSource> source, Func<TSource, TKey> keySelector, IBucketComparer<TKey> comparer)
    {
        return new BucketSortedEnumerable<TSource, TKey>(source, keySelector, comparer, true);
    }

    public static IOrderedEnumerable<TSource> ThenWithDomainBy<TSource, TKey>(this IOrderedEnumerable<TSource> source, Func<TSource, TKey> keySelector, IEnumerable<TKey> keyDomain)
    {
        return source.CreateOrderedEnumerable(keySelector, new BucketComparer<TKey>(keyDomain), false);
    }

    public static IOrderedEnumerable<TSource> ThenWithDomainBy<TSource, TKey>(this IOrderedEnumerable<TSource> source, Func<TSource, TKey> keySelector, IBucketComparer<TKey> comparer)
    {
        return source.CreateOrderedEnumerable(keySelector, comparer, false);
    }

    public static IOrderedEnumerable<TSource> ThenWithReversedDomainBy<TSource, TKey>(this IOrderedEnumerable<TSource> source, Func<TSource, TKey> keySelector, IEnumerable<TKey> keyDomain)
    {
        return source.CreateOrderedEnumerable(keySelector, new BucketComparer<TKey>(keyDomain), true);
    }

    public static IOrderedEnumerable<TSource> ThenWithReversedDomainBy<TSource, TKey>(this IOrderedEnumerable<TSource> source, Func<TSource, TKey> keySelector, IBucketComparer<TKey> comparer)
    {
        return source.CreateOrderedEnumerable(keySelector, comparer, true);
    }

}
```

しれっとLINQっぽい名前に変えました。で、肝心の使い方ですが、2通りあります。
まずは最初の方でやっていた、keyDomainを指定する方法。

```
source.OrderWithDomainBy(v => v.Item1, Enumerable.Range(0, 100))
      .ThenWithReversedDomainBy(v => v.Item2, Enumerable.Range(0, 100))
```

こんな感じでItem1で昇順に並べた後、Item2で降順に並べます。
昇順や降順というのはkeyDomainの並びに依存して、Reversedがつかない方はkeyDomainの順番で、つく方は逆順でということになります。

もう1つの方はkeyDomainを指定しない方法。値の範囲がわからない場合に使えますが、バケットソートの性質上、あまり使わない方がいいと思います。

```
class MyComparer : IBucketComparer<int> {

    public IEnumerable<int> KeyDomain { get { return null; } }

    public int Compare(int lhs, int rhs)
    {
        return lhs - rhs;
    }

}

var comparer = new MyComparer();
source.OrderWithDomainBy(v => v.Item1, comparer)
      .ThenWithReversedDomainBy(v => v.Item2, comparer)
```

IBucketComparerを実装したクラスを作り、KeyDomainをnullで返すと、ソートの際に一度sourceを走査してキーを洗い出し、Compareに従って並べ替えてkeyDomainを作成します。
想定外にbucketsの数が増える可能性もあるのでご利用は計画的に。

# 余談
もしかしたらこの実装は厳密に言うと鳩の巣ソートかもしれません。
あと、軽くググって見つからなかったので作ってみた（そして、結局使わなかったのでここに供養することにした）のですが、こんな感じのものは太古の昔に誰かが作ってそうなんですが、どうでしょう？