Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- this gist demonstrates idiomatic way to do sorting of various kinds through functional programming
- ```scala
- import scala.math.Ordering
- import scala.util.control.TailCalls._
- trait Sort {
- def sort[O: Ordering](xs: List[O]): List[O]
- def safeSort[O: Ordering](xs: List[O]): List[O]
- }
- class InsertionSort extends Sort {
- def sort[O](ls: List[O])(implicit Ord: Ordering[O]): List[O] = {
- def insert(x: O, xs: List[O]): List[O] =
- xs match {
- case Nil => List(x)
- case y :: ys =>
- if (Ord.compare(x, y) < 0) x :: y :: ys
- else y :: insert(x, ys)
- }
- ls match {
- case Nil => Nil
- case x :: xs => insert(x, sort(xs))
- }
- }
- private def isort[O](ls: List[O])(implicit Ord: Ordering[O]): TailRec[List[O]] = {
- def insert(x: O, xs: List[O]): TailRec[List[O]] =
- xs match {
- case Nil => done(List(x))
- case y :: ys =>
- if (Ord.compare(x, y) < 0) done(x :: y :: ys)
- else insert(x, ys).map(y :: _)
- }
- ls match {
- case Nil => done(Nil)
- case x :: xs =>
- isort(xs).flatMap(insert(x, _))
- }
- }
- override def safeSort[O: Ordering](xs: List[O]): List[O] = isort(xs).result
- }
- class SelectionSort extends Sort {
- def sort[O](ls: List[O])(implicit Ord: Ordering[O]): List[O] = {
- def select(xs: List[O]): (O, List[O]) =
- xs match {
- case Nil => throw new RuntimeException("not possible")
- case x :: Nil => (x, Nil)
- case y :: ys =>
- val (z, zs) = select(ys)
- if (Ord.compare(y, z) < 0) (y, z :: zs)
- else (z, y :: zs)
- }
- ls match {
- case Nil => Nil
- case _ =>
- val (x, xs) = select(ls)
- x :: sort(xs)
- }
- }
- private def isort[O](ls: List[O])(implicit Ord: Ordering[O]): TailRec[List[O]] = {
- def select(xs: List[O]): TailRec[(O, List[O])] =
- xs match {
- case Nil => throw new RuntimeException("not possible")
- case x :: Nil => done((x, Nil))
- case y :: ys =>
- select(ys) map { case (z, zs) =>
- if (Ord.compare(y, z) < 0) (y, z :: zs)
- else (z, y :: zs)
- }
- }
- ls match {
- case Nil => done(Nil)
- case _ =>
- select(ls).flatMap { case (x, xs) =>
- isort(xs).map(x :: _)
- }
- }
- }
- override def safeSort[O: Ordering](xs: List[O]): List[O] = isort(xs).result
- }
- ```
Add Comment
Please, Sign In to add comment