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