C# Linqでクイックソート

2009-09-30

qsort []     = []
qsort (x:xs) = qsort elts_lt_x ++ [x] ++ qsort elts_greq_x
                 where
                   elts_lt_x   = [y | y <- xs, y < x]
                   elts_greq_x = [y | y <- xs, y >= x]

これはHaskellのコードで、良く見かける定番のQuickSort。うん、短い。というわけでLinqでそれをやる。というネタは既出のン番煎じなのですが、気にせずやる。

// LinqでHaskell風のクイックソート
public static IEnumerable<T> QuickSort<T>(IEnumerable<T> source)
    where T : IComparable<T>
{
    if (!source.Any()) return source;
    var pivot = source.First();
    return source
        .GroupBy(x => x.CompareTo(pivot))
        .OrderBy(g => g.Key) // OrderBy使うのはどうかなー、というところはある
        .SelectMany(g => (g.Key == 0) ? g : QuickSort(g));
}

GroupBy->SelectManyと流れるように書けて美しいー。これならHaskellにも引けを取らないですね！但し問題なのは、OrderByを使用しているところ。CompareToの結果である-1, 0, 1を並べ替えるために使っているのだけど、OrderByの中身はシュワルツ変換の挟まったクイックソートそのものなので邪道な感は否めない。OrderBy使うなら、そもそもsource.OrderBy(x => x)でもいいぢゃん、って話になってしまう。

// 非GroupBy版。LookupはGroupByの即時評価版と考えていい。
public static IEnumerable<T> QuickSort<T>(IEnumerable<T> source)
    where T : IComparable<T>
{
    if (!source.Any()) return source;
    var pivot = source.First();
    var lookup = source.ToLookup(x => x.CompareTo(pivot));
    return QuickSort(lookup[-1]).Concat(lookup[0]).Concat(QuickSort(lookup[1]));
}

GroupByをToLookupに書き変えました。ToLookupはGroupByの即時評価版といった感じで、インデクサによるアクセスが可能。インデクサ使わないでそのままforeachで列挙する、なんて時はGroupByを使った方が良いです。今回はインデクサで順番を明示的に指定するため、ToLookupでパーティション切って、Concatで繋いでやれば出来あがり。やってることが非常に分かりやすくて良い。ソースの見た目も中々綺麗じゃないでしょうか。Haskellのものとも非常に近いです(ようするに++がConcatなので) ToLookupではなくWhereを使えば、見た目は更にHaskellに近づきますが、列挙が二回になるので、ここはToLookupで。

// 普通に？書いた場合。
public static void QuickSort<T>(IList<T> source, int lowerBound, int upperBound)
    where T : IComparable<T>
{
    var pivot = source[lowerBound + ((upperBound - lowerBound) >> 1)];
    var left = lowerBound - 1;
    var right = upperBound + 1;
    while (true)
    {
        while (source[++left].CompareTo(pivot) < 0) ;
        while (source[--right].CompareTo(pivot) > 0) ;
        if (left >= right) break;
        var temp = source[left];
        source[left] = source[right];
        source[right] = temp;
    }
    if (lowerBound < left - 1) QuickSort(source, lowerBound, left - 1);
    if (right + 1 < upperBound) QuickSort(source, right + 1, upperBound);
}

今度は非Linqに一般的？な書き方で。あまりヘタな書き方するとアレだなあ、と思ったので404 Blog Not Found:javascript - Array#sortはオレquicksortより遅い by ChromeのコードをC#に移植しました。あたしこの書き方嫌いなのよね、という感じにゴチャゴチャした印象は否めないというか、まあ、嫌いなのよね。一本の配列で頑張るところが、ゆとりな私としてはしんどい。ビットシフトも嫌よね。

public static IEnumerable<T> QuickSort<T>(IEnumerable<T> source)
    where T : IComparable<T>
{
    var enumerator = source.GetEnumerator();
    if (!enumerator.MoveNext()) yield break;

    var pivot = enumerator.Current;
    var less = new List<T>();
    var equal = new List<T>();
    var greater = new List<T>();
    do
    {
        switch (enumerator.Current.CompareTo(pivot))
        {
            case -1: less.Add(enumerator.Current); break;
            case 0: equal.Add(enumerator.Current); break;
            case 1: greater.Add(enumerator.Current); break;
        }
    } while (enumerator.MoveNext());

    foreach (var item in QuickSort(less)) yield return item;
    foreach (var item in equal) yield return item;
    foreach (var item in QuickSort(greater)) yield return item;
}

最後に、非Linqで、ToLookup版を再現してみたものを。do-whileがToLookupでforeachの連発がConcat。ようするに富豪的にListを作りまくるってわけなんですね！書きやすいし分かりやすいので、一本配列版よりも遥かに好き度高い。現代人はListを贅沢に大量に好きなだけ使うのです。まあ、Linq版がない状態でこの書き方が浮かぶ or 実行に移せるかどうかといったら、かなり無理ですけど。

C# Linqでクイックソート

Profile

Archive