Quicksort (Scala)

Other implementations: AWK | C | C++ | Eiffel | Erlang | Forth | Haskell | Java | JavaScript | Mathematica | Mercury | Oz | Python | Python, arrays | Scala | Sed | Standard ML | Visual Basic .NET | XProc

A recursive implementation of Quicksort in Scala.

Array Quicksort

There are a couple of examples of Array Quicksort in the tutorial (A First Example page) in the form of in-place array sort as well as in the term rewriting style.

List Quicksort

```<<ListQuicksort>>=
def sort[A <% Ordered[A]](xs: List[A]):List[A] = {
if (xs.isEmpty || xs.tail.isEmpty) xs
else {
val pivot = xs( xs.length / 2)
// list partition
// initialize boxes
var lows: List[A] = Nil
var mids: List[A] = Nil
var highs: List[A] = Nil
for( val item <- xs) {
// classify item
if ( item == pivot) mids = item :: mids
else if (item < pivot) lows = item :: lows
else highs = item :: highs
}
// return sorted list appending chunks
sort( lows) ::: mids ::: sort( highs)
}
}
```

An alternative using recursion and pattern matching...

```<<ListQuicksort1>>=
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))
}
}
```

Test module

```<<QuicksortTest.scala>>=
package test;
import scala.testing.UnitTest ;
object QuicksortTest extends Application {
ListQuicksort
def listSortTest = {
UnitTest.assertEquals( sort[String]( List( "Berlin", "Paris", "Barcelona", "Amsterdam"))
, List( "Amsterdam", "Barcelona", "Berlin", "Paris")) ;
UnitTest.assertEquals( sort[Int]( List(5,6,4,2,3,1)), List(1,2,3,4,5,6)) ;
UnitTest.assertEquals( sort[Int]( List(2,1)),List(1,2)) ;
UnitTest.assertEquals( sort[Int]( List(1)),List(1)) ;
UnitTest.assertEquals( sort[Int]( List()),List()) ;
}
Console.println ;
Console.println("listSortTest") ;
listSortTest ;
}
```

Testing

```scala test.QuicksortTest
listSortTest
passed ok
passed ok
passed ok
passed ok
passed ok
```