Quicksort (Scala)

From LiteratePrograms

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.

Contents 1 Array Quicksort 2 List Quicksort 3 Test module 4 Testing

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

Download code