クイックソート

作ってみる。

scala> def qsort[T <% Ordered[T]](xs: List[T]): List[T] = xs match {
     |   case List() => List()
     |   case y::ys =>
     |     qsort(ys filter(_ < y)):::List(y):::qsort(ys filter(y <= _))
     | }
qsort: [T](List[T])(implicit (T) => Ordered[T])List[T]

scala> qsort(List(2, 44, 5, 3, 1, 3, 9, 56, 7, 8, 3, 9, 9, 43, 2))
res0: List[Int] = List(1, 2, 2, 3, 3, 3, 5, 7, 8, 9, 9, 9, 43, 44, 56)

参考:
プログラミングHaskellをScalaで解く - DiaryException



同じやつを再帰に含めない。

scala> def qsort[T <% Ordered[T]](xs: List[T]): List[T] = xs match {
     |   case List() => List()
     |   case y::ys =>
     |     qsort(ys filter(_ < y)):::
     |     (y::(ys filter(_ == y))):::
     |     qsort(ys filter(y < _))
     | }
qsort: [T](List[T])(implicit (T) => Ordered[T])List[T]

scala> qsort(List(2, 44, 5, 3, 1, 3, 9, 56, 7, 8, 3, 9, 9, 43, 2))
res0: List[Int] = List(1, 2, 2, 3, 3, 3, 5, 7, 8, 9, 9, 9, 43, 44, 56)


こうして見ると、クイックソートって直感的だったんだなぁ。
どうやって並べ替えるかというよりも、並べ替えた後の状態をただ記述してるだけな感じ。