Quicker
sort?
Quicker
sort!
Sorting: what and how?
Merge Sort
Insertion Sort
Bubble Sort
Quicksort
Bogosort
All rely on cmp
def cmp(a: T, b: T): Boolean
def sort[T](xs: List[T], cmp: (T,T) => Boolean): List[T]
Herman Hollerith
Counting Sort
Radix Sort
Bucket Sort
O(n)
O(n+m)
n, number of elementsm, the max length of an element
...but they aren't general
They rely on the structure of the data.
T => ???
Fritz Henglein
def dsort[T](xs: List[T], ???: ???): List[T]
def dsort[T](xs: List[T], ordering: ???): List[T]
def dsort[T](xs: List[T], ordering: Order[T]): List[T]
case class NatOrd extends Order[Int]
case class NatOrd(i: Int) extends Order[Int]
def dsort[A,B](ord: Order[A], xs: List[(A,B)]): List[List[B]] =
ord match {
case NatOrd => ???
}
def dsort[A,B](ord: Order[A], xs: List[(A,B)]): List[List[B]] =
ord match {
case NatOrd(n) => bucketSort(xs,n)
}
case class NatOrd(i: Int) extends Order[Int]
case class SumOrd[A,B](oleft: Order[A], oright: Order[B]) extends Order[A\/B]
def dsort[A,B](ord: Order[A], xs: List[(A,B)]): List[List[B]] =
ord match {
case NatOrd(n) => bucketSort(xs,n)
case SumOrds(oleft,oright) =>
dsort(oleft,xs.lefts) ++ dsort(oright,xs.rights)
}
case class NatOrd(i: Int) extends Order[Int]
case class SumOrd[A,B](oleft: Order[A], oright: Order[B]) extends Order[A\/B]
case class ProdOrd[A,B](a_ord: Order[A], b_ord: Order[B]) extends Order[(A,B)]
def dsort[A,B](ord: Order[A], xs: List[(A,B)]): List[List[B]] =
ord match {
case NatOrd(n) => bucketSort(xs,n)
case SumOrds(oleft,oright) =>
dsort(oleft,xs.lefts) ++ dsort(oright,xs.rights)
case ProdOrd(aord,bord) =>
for { ys <- dsort(orda,xs map retuple);
vs <- dsort(ordb,ys) } yield vs
}
case class NatOrd(i: Int) extends Order[Int]
case class SumOrd[A,B](oleft: Order[A], oright: Order[B]) extends Order[A\/B]
case class ProdOrd[A,B](a_ord: Order[A], b_ord: Order[B]) extends Order[(A,B)]
case class MapOrd[A,B](f: A => B, b_ord: Order[B]) extends Order[A]
def dsort[A,B](ord: Order[A], xs: List[(A,B)]): List[List[B]] =
ord match {
case NatOrd(n) => bucketSort(xs,n)
case SumOrds(oleft,oright) =>
dsort(oleft,xs.lefts) ++ dsort(oright,xs.rights)
case ProdOrd(aord,bord) =>
for { ys <- dsort(orda,xs map retuple);
vs <- dsort(ordb,ys) } yield vs
case Map0(f,ordb) =>
xs map { case (a,c) => (f(a),c) } |> dsort(ordb,_)
}
case class NatOrd(i: Int) extends Order[Int]
case class SumOrd[A,B](oleft: Order[A], oright: Order[B]) extends Order[A\/B]
case class ProdOrd[A,B](a_ord: Order[A], b_ord: Order[B]) extends Order[(A,B)]
case class MapOrd[A,B](f: A => B, b_ord: Order[B]) extends Order[A]
case class TrivOrd[A]() extends Order[A]
def dsort[A,B](ord: Order[A], xs: List[(A,B)]): List[List[B]] =
ord match {
case NatOrd(n) => bucketSort(xs,n)
case SumOrds(oleft,oright) =>
dsort(oleft,xs.lefts) ++ dsort(oright,xs.rights)
case ProdOrd(aord,bord) =>
for { ys <- dsort(orda,xs map retuple);
vs <- dsort(ordb,ys) } yield vs
case Map0(f,ordb) =>
xs map { case (a,c) => (f(a),c) } |> dsort(ordb,_)
case TrivOrd() => List(xs map { _._2 })
}
...
case class ListOrd[A](ord: Order[A]) extends Order[List[A]]
def dsort[A,B](ord: Order[A], xs: List[(A,B)]): List[List[B]] =
ord match {
...
case ListOrd(ord) => ???
}
How do I order Lists?
How do I order Lists?
List() < List(...)
How do I order Lists?
List() < List(...)
List(a,...) < List(b,...)
How do I order Lists?
List() < List(...)
List(a,...) < List(b,...)
List(a,a,...) < List(b,b...)
def dsort[A,B](ord: Order[A], xs: List[(A,B)]): List[List[B]] =
ord match {
...
case ListOrd(ord) =>
val new_order =
MapOrd(toHeadTailTuple,
SumOrd(TrivOrd(),
ProdOrd(ord,
ListOrd(ord))))
dsort(new_order, xs)
}
MapOrd(toHeadTailTuple,
SumOrd(TrivOrd(),
ProdOrd(ord, ListOrd(ord))))
def toHeadTailTuple[A,B](elt: List[B]): (A\/B,List[B])
def toHeadTailTuple[A,B](elt: List[B]): A\/(B,List[B]) =
elt.headOption match {
case None => ().left
case Some(h) => (h,elt.tail).right
}
["ba","bba","c"]
["ba","bba","c"]
[("ba","ba"),("bba","bba"),("c","c")]
["ba","bba","c"]
[("ba","ba"),("bba","bba"),("c","c")]
[([b,a],"ba"),([b,b,a],"bba"),([c],"c")]
["ba","bba","c"]
[("ba","ba"),("bba","bba"),("c","c")]
[([b,a],"ba"),([b,b,a],"bba"),([c],"c")]
[(Right((b,[a])),"ba"),
(Right((b,[b,a])),"bba"),(Right((c,[])),"c")]
...
[(Right((b,[a])),"ba"),
(Right((b,[b,a])),"bba"),(Right((c,[])),"c")
[((b,[a]),"ba"),((b,[b,a]),"bba"),((c,[]),"c")]
[(b,([a],"ba")),(b,([b,a],"bba")),(c,([],"c"))]
...
[((b,[a]),"ba"),((b,[b,a]),"bba"),((c,[]),"c")]
[(b,([a],"ba"),(b,([b,a],"bba")),(c,([],"c"))]
[(2,([a],"ba"),(2,([b,a],"bba")),(3,([],"c"))]
...
[(2,([a],"ba"),(2,([b,a],"bba")),(3,([],"c"))]
[[([a],"ba"),([b,a],"bba")], [([],"c")]]
...
[[([a],"ba"),([b,a],"bba")], [([],"c")]]
[((a,[]),"ba"),((b,[a]),"bba"))] ++ [["c"]]
...
[((a,[]),"ba"),((b,[a]),"bba"))] ++ [["c"]]
[[([],"ba")],[([a],"bba")]] ++ [["c"]]
...
[[([],"ba")],[([a],"bba")]] ++ [["c"]]
[["ba"]] ++ [["bba"]] ++ [["c"]]
...
["ba", "bba", "c"]
So how fast is it?
