Eine generische quicksort in Scala

Question

Ich habe um mit Scala vor kurzem spielen und dachte darüber nach, wie eine generische Version von quicksort darin zu implementieren (nur ein besseres Gefühl für die Sprache zu bekommen)

ich kam mit so etwas wie dies

object Main { 
    def qs[T](a: List[T], f: (T, T) => Boolean): List[T] = { 
    if (a == Nil) return a 
    val (l, g) = a drop 1 partition (f(a(0),(_:T))) 
    qs(l, f) ::: List(a(0)) ::: qs(g, f) 
    } 

    def main(args: Array[String]): Unit = { 
    val a = List(5,3,2,1,7,8,9,4,6) 
    val qsInt = qs(_: List[Int], (_: Int) > (_: Int)) 
    println(qsInt(a)) 
    } 

} 

Dies ist nicht so allgemein wie ich es wollte, da ich explizit muß angeben, wie die Elemente eher bestellen dann etwas nur tun, wie

val (l, g) = a drop 1 partition (a(0) >) 

Wie kann ich dem Compiler mitteilen, dass T nur den Größer-als-Operator implementieren muss, um von dieser Funktion sortiert werden zu können?

Grüße

Answer 1

def qsort[T <% Ordered[T]](list: List[T]): List[T] = { 
    list match { 
    case Nil => Nil  
    case x::xs =>   
    val (before, after) = xs partition (_ < x) 
    qsort(before) ++ (x :: qsort(after)) 
    } 
} 

Answer 2

Seit Rogercovered der Ordered Fall, lassen Sie mich Ordering abdecken:

def qsort[T](list: List[T])(implicit ord: Ordering[T]): List[T] = list match { 
    // import ord._ // enables "_ < x" syntax 
    case Nil => Nil 
    case x :: xs => 
    val (before, after) = xs partition (ord.lt(_, x)) 
    qsort(before) ::: x :: qsort(after) 
} 

Mit Ordering zwei Vorteile hat:

1. Der T Typ muss nicht bien haben n erstellt als Ordered.
2. Man kann leicht alternative Anordnungen bereitstellen.

Zum Beispiel auf Scala 2.8:

def sortIgnoreCase(strs: List[String]) = { 
    val myOrdering = Ordering.fromLessThan { (x: String, y: String) => 
    x.toLowerCase < y.toLowerCase 
    } 
    qsort(strs)(myOrdering) 
}