Quicksort in Scala
by Lars Vogel / November 13th, 2009
Scala allows to define very short and precise the intension of the programmer. To demonstrate this I use Quicksort as an Example.
The following is an implementation of quicksort in Scala.
package de.vogella.scala.quicksort
/* Quicksort in Scala */
class Quicksort {
def sort(a:Array[Int]): Array[Int] =
if (a.length < 2) a
else {
val pivot = a(a.length / 2)
sort (a filter (pivot>)) ++ (a filter (pivot == )) ++
sort (a filter(pivot <))
}
}
And a little test
package de.vogella.scala.quicksort
object Test {
def main(args: Array[String]) = {
val quicksort = new Quicksort
val a = Array(5, 3, 2, 2, 1, 1, 9, 39 ,219)
quicksort.sort(a).foreach(n=> (print(n), print (" " )))
}
}
To learn more about Scala check out this introduction tutorial: Scala development with Eclipse
Update: this example is similar to the quicksort example from the excellent online Scala by Example book. Caution: The link is a pdf document.
Tags: Scala
Filed under: Scala
November 13th, 2009 at 1:32 pm
How beautiful and concise! One concern, though: Quicksort should rather be an object, aint’t it?
November 13th, 2009 at 4:09 pm
@thSoft: You are right. I adjusted the code. Thanks for the feedback.
Update: The Eclipse Scala plugin gave me an error by using Object. I changed it back to class for avoid this error but I agree using object would be better.
November 13th, 2009 at 4:21 pm
You ripped this off of Scala by Example. At the very least, credit your source.
http://www.scala-lang.org/docu/files/ScalaByExample.pdf
November 13th, 2009 at 5:17 pm
@JohnDoe Thanks for the source. I actually did not rip this off this book which I did not read so far. I was watching a screencast from Ted Neward there he discussed Quicksort in Scala and in this presentation he had an error:
if (array.length <= 1) array
was in this presentation if (array.length == 1) array and I figured I should post a correction.
November 13th, 2009 at 5:25 pm
@JohnDoe: I added the link to the Scala book in the blog post.
November 13th, 2009 at 6:41 pm
Fair enough. Thx
November 13th, 2009 at 6:42 pm
if (array.length <2) array is slightly better
November 13th, 2009 at 6:47 pm
@XXX I would agree that this saves one sign and that this is good. But other then that does this makes a difference? Anyway I adjusted the code, less is more.
November 13th, 2009 at 9:46 pm
Is there a benchmark comparison to a java array based quicksort available?
How are the memory requirements – is the compiler able to generate bytecode that uses int[]?
What happens with a sort(sort: Array[Number])?
November 13th, 2009 at 10:08 pm
Comparing to groovy quicksort impl:
def quickSort(lst){
if(lst.size()
if(item < pivot){ less.add(item)}
else{greater.add(item)}
}
return quickSort(less)+[pivot]+quickSort(greater)
}
I find "return quickSort(less)+[pivot]+quickSort(greater)" more concise, but you can override the + operator in scala to append lists. Or does it behave that way by default?
November 13th, 2009 at 10:22 pm
@Noct: To my knowledge Scala does not define function “+” on Array. See also http://www.scala-lang.org/docu/files/api/scala/Array$object.html
November 13th, 2009 at 11:24 pm
http://www.scala-lang.org/docu/files/api/scala/Array.html
override def ++[B >: A](that : Iterable[B]) : Array[B]
Returns an array consisting of all elements of this array followed by all elements of the argument iterable.
November 13th, 2009 at 11:45 pm
@JohnDoe: Nice & thanks. Coding updated, I also find this representation more concise.
November 14th, 2009 at 3:44 am
This is the JavaFX Script version for a QuickSort function:
function sort(a: Integer[]): Integer[]
{
if (sizeof a < 2) a
else {
def pivot = a[sizeof a / 2];
[sort(a[n | n pivot])];
}
}
November 14th, 2009 at 3:48 am
The last line above got truncated; it should be:
[sort(a[n | n < pivot]), a[n | n == pivot], sort(a[n | n > pivot])];
November 15th, 2009 at 7:12 am
Thanks for the example. Would it look similar with a list of Comparable objects rather than a specific Int type? I posted related thoughts about conciseness here, referencing this post, along with a sample Groovy implementation:
http://chriswongdevblog.blogspot.com/2009/11/on-conciseness.html