Skip to content

Instantly share code, notes, and snippets.

@bmarcot
Created January 27, 2015 09:48
Show Gist options
  • Save bmarcot/11c253d498e79643cb86 to your computer and use it in GitHub Desktop.
Save bmarcot/11c253d498e79643cb86 to your computer and use it in GitHub Desktop.
import scala.util.Random.nextInt
def choosePivot(xs: List[Int]): Int = {
if (xs.isEmpty) 0
else xs(nextInt(xs.length))
}
def quicksort(xs: List[Int], p: Int): List[Int] = {
if (xs.isEmpty) List()
else if (xs.length == 1) xs
else {
val ys: (List[Int], List[Int]) = xs.partition(_ < p)
quicksort(ys._1, choosePivot(ys._1)) ::: quicksort(ys._2, choosePivot(ys._2))
}
}
val xs = List(4,2,9,1,3,6)
println(quicksort(xs, choosePivot(xs)))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment