クイックソート

クロージャが使えるようになったので、クイックソートを書いてみました。

function qsort(src : ArrayList, dest : ArrayList)
{
  if (src.Count == 0) return;
  
  var x = src.Ptr[0];
  ArrayList lt, ge;
  lt |< src.FindPartial(1, \y => y <  x);
  ge |< src.FindPartial(1, \y => y >= x);
  dest |< lt.qsort;
  dest |< Add(x);
  dest |< ge.qsort;
} 

パイプ演算子はシンタックスシュガーですが、F#を参考にしました。

有名なHaskellのクイックソートを意識しています。Haskellのコードは以下の通りです。

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

Haskellの簡潔さには太刀打ちできませんが、今はこのくらいが限界です。