Quicksort in Scala

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.

About Lars Vogel

Lars Vogel is the founder and CEO of the vogella GmbH and works as Eclipse and Android consultant, trainer and book author. He is a regular speaker at international conferences, He is the primary author of vogella.com. With more than one million visitors per month this website is one of the central sources for Java, Eclipse and Android programming information.
This entry was posted in Java and tagged . Bookmark the permalink.

16 Responses to Quicksort in Scala

  1. thSoft says:

    How beautiful and concise! One concern, though: Quicksort should rather be an object, aint’t it?

  2. Lars Vogel says:

    @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.

  3. JohnDoe says:

    You ripped this off of Scala by Example. At the very least, credit your source.
    http://www.scala-lang.org/docu/files/ScalaByExample.pdf

  4. Lars Vogel says:

    @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.

  5. Lars Vogel says:

    @JohnDoe: I added the link to the Scala book in the blog post.

  6. JohnDoe says:

    Fair enough. Thx

  7. XXX says:

    if (array.length <2) array is slightly better :)

  8. Lars Vogel says:

    @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. :-)

  9. NN says:

    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])?

  10. Noct says:

    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?

  11. Lars Vogel says:

    @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

  12. JohnDoe says:

    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.

  13. Lars Vogel says:

    @JohnDoe: Nice & thanks. Coding updated, I also find this representation more concise.

  14. Rogério Liesenfeld says:

    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])];
    }
    }

  15. Rogério Liesenfeld says:

    The last line above got truncated; it should be:

    [sort(a[n | n < pivot]), a[n | n == pivot], sort(a[n | n > pivot])];

  16. Chris Wong says:

    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

Comments are closed.