Scala algorithm: Quick Sort sorting algorithm in pure immutable Scala

Published , last updated

Algorithm goal

Quick sort is a standard merging algorithm, and uses a similar divide-and-conquer approach to MergeSortStackSafe. Where it differs is that it works around a pivot.

Sorting a list eg \([3,2,1]\) should return \([1,2,3]\).

Most interesting thing is that a two-pivot Quicksort is the default sorting implementation for Java.

Do note that this implementation is not stack-safe, it will throw a StackOverflowError when you throw 1M items at it.

We will cover the topic of stack-safe algorithms (including Quicksort) in future, by applying something called 'Defunctionalisation' which turns the implicit call stack into an explicit one that you pass around.

Test cases in Scala

assert(quickSort(List.empty[Int]) == List.empty[Int])
assert(quickSort(List(1)) == List(1))
assert(quickSort(List(1, 2)) == List(1, 2))
assert(quickSort(List(2, 1)) == List(1, 2))
assert(quickSort(List(2, 1, 3)) == List(1, 2, 3))
assert(quickSort(List(2, 1, 4, 3)) == List(1, 2, 3, 4))
assert(quickSort(List(2, 4, 5, 1, 3)) == List(1, 2, 3, 4, 5))
assert(
  {
    val randomArray = scala.util.Random
      .nextBytes(1000 + Math.abs(scala.util.Random.nextInt(100)))
      .map(_.toInt)
      .toList
    quickSort(randomArray) == randomArray.sorted
  },
  "A random array of a ~1000 length is sorted"
)

Algorithm in Scala

8 lines of Scala (version 2.13), showing how concise Scala can be!

Get the full algorithm Scala algorithms logo, maze part, which looks quirky!

or

'Unlimited Scala Algorithms' gives you access to all the Scala Algorithms!

Upon purchase, you will be able to Register an account to access all the algorithms on multiple devices.

Stripe logo

Explanation

We follow the standard definition of quicksort. Scala's partition creates a tuple of values to the left of the pivot, and values to not to the left. (this is © from www.scala-algorithms.com)

Scala concepts & Hints

  1. Pattern Matching

    Pattern matching in Scala lets you quickly identify what you are looking for in a data, and also extract it.

    assert("Hello World".collect {
      case character if Character.isUpperCase(character) => character.toLower
    } == "hw")
    

View the rest of Scala algorithms