「Groovy イン・アクション」を読んでる。今 93 ページ だ。
リストを使ったクイックソートのサンプルが載ってたので試してみた。（一部改変）
P.93 4.10 リストを使ったクイックソート
def quickSort(list) { if (list.size() < 2) return list def pivot = list[list.size().intdiv(2)] def left = list.findAll { it < pivot } def middle = list.findAll { it == pivot } def right = list.findAll { it > pivot } return (quickSort(left) + middle + quickSort(right)) } assert quickSort([]) == [] assert quickSort([1]) == [1] assert quickSort([1, 2]) == [1, 2] assert quickSort([2, 1]) == [1, 2] assert quickSort([2, 1, 3]) == [1, 2, 3] assert quickSort([2, 1, 3, 2]) == [1, 2, 2, 3] assert quickSort([3, 2, 1, 2]) == [1, 2, 2, 3] assert quickSort([1.0f, 'a', 100, null]) == [null, 1.0f, 'a', 100] assert quickSort('Karin and Dierk') == ' DKaadeiiknnrr'.toList()
quickSort を呼び出してる最後2行が凄い！
これの何が凄いかって、型が異なる物もソート出来てるって所が凄いなぁと。（数値型と文字列型）
一番最後の呼び出しなんか、ただの文字列渡してるのにソートされてる。
一応 C# でも試してみた。
static List<T> QuickSort<T>(List<T> list) where T : IComparable
{
if (list.Count < 2) return list;
var pivot = list[list.Count % 2];
var left = list.FindAll(m => m.CompareTo(pivot) < 0);
var middle = list.FindAll(m => m.CompareTo(pivot) == 0);
var right = list.FindAll(m => m.CompareTo(pivot) > 0);
var ret = new List<T>();
ret.AddRange(QuickSort(left));
ret.AddRange(middle);
ret.AddRange(QuickSort(right));
return ret;
}
static void Main(string args)
{
QuickSort(new List<IComparable>()).ForEach(Console.Write);
Console.WriteLine();
QuickSort(new List<IComparable> { 1 }).ForEach(Console.Write);
Console.WriteLine();
QuickSort(new List<IComparable> { 2, 1 }).ForEach(Console.Write);
Console.WriteLine();
QuickSort(new List<IComparable> { 2, 1, 3 }).ForEach(Console.Write);
Console.WriteLine();
QuickSort(new List<IComparable> { 2, 1, 3, 2 }).ForEach(Console.Write);
Console.WriteLine();
// コンパイルは通るが実行時例外が発生する。
// (String.CompareTo の パラメータは、String 型じゃないとダメ！)
//QuickSort(new List<IComparable> {1.0f, "a", 100, null }).ForEach(Console.Write);
//Console.WriteLine();
// 並び替え出来ない！
QuickSort(new List<IComparable> { "Karin and Dierk" }).ForEach(Console.Write);
Console.WriteLine();
Console.ReadLine();
}
クイックソートの実装箇所は、ほぼ同じような感じで実装出来る。
※System.Collections.Generic.List<T> を使ってるのは、FindAll メソッドがあったから。
LINQ を使えば List<T> じゃなくても似たようなコード量で実装出来そう。
でも、異なる型がある物はソート出来なかった（実行時例外）し、そもそも文字列を渡す事も出来ない。
※実行時例外が発生したのは、IComparable の実装次第なのでカスタム文字列型を作れば数値とも比較出来るはず。
C# はジェネリックを使用して実装したけど、このクイックソートを使えるのが IComparable を実装している型に限られる。
これを Groovy みたいな事が出来るようにしようとすると、
System.Reflection 名前空間 を使えば 何とか出来ると思うけど、メソッドやプロパティ名が統一されてないから条件分岐が多発しそうで現実的じゃない。。
