How to do Quicksort in Haskell

Overview

Haskell is a functional programming language, a programming paradigm that focuses on changing data through expressions that don’t have side effects. These expressions are often called pure functions.

Let’s see how to implement one of the most popular sorting algorithms, Quicksort in Haskell.

Algorithm

The quicksort function uses the “divide and conquer” technique for sorting:

We choose a pivot element from the list and divide the list into two halves, such that elements less than and equal to the pivot are placed on the left side, and elements greater than the pivot are placed on the right.
We repeat the above process for the resulting left and right subarrays until we end up with a list of size 1.
At this stage, all elements are already sorted, and we combine all the results to return the final sorted list.

Code

Let’s translate the above algorithm into a Haskell program:

-- Return the list which contains elements less than or equal to the input element
smallerEq :: Int -> [Int] -> [Int]
smallerEq = \v -> \list ->
    case list of
        [] -> []
        x:xs | x<=v -> x:smallerEq v xs
        _:xs -> smallerEq v xs
-- Return the list which contains elements greater than the specified element
greater :: Int -> [Int] -> [Int]
greater = \v -> \list ->
    case list of
        [] -> []
        x:xs | x>v -> x:greater v xs
        _:xs -> greater v xs
-- Sort a list using the quicksort algorithm 
qsort :: [Int] -> [Int]
qsort = \list ->
    case list of
        [] -> []
        x:xs -> 
            qsort (smallerEq x xs) ++ x:qsort (greater x xs)

Explanation

`smallerEq` function

We write the smallerEq function, which returns a list containing elements smaller or equal to the input element.

Line 2: The type annotation, smallerEq :: Int -> [Int] -> [Int], shows that our function takes an integer (pivot element) and a list of integers and returns a list of integers.
Line3 to 4: We use the function definition, which shows that our function takes a list and element v, followed by a case expression that implements the recursive formulation of the problem.
Line 6: x:xs is a syntax in Haskell that destructures a list into its head element and the remainder list. If the input element is less than or equal to the head element, we return the list x:smallerEq v xs. This places the head element in the final list and combines it with all the results from the recursive call on the remaining list.
Line 7: The final case statement implements the flip scenario. If the input element is greater than the head element x, then x is not part of the final list hence it returns the recursive call smallerEq v xs, which combines the result from the remaining list.

`greater` function

The greater function returns a list containing elements greater than the input element. The greater function is written exactly the same as the smallerEq function but with the <= sign replaced with the > sign. The logic otherwise is the same as above.

`quicksort` function

Let’s put all the pieces together.

Line 20: The first case statement implements the base case. If the input list is empty, then there is nothing to sort, and therefore we return an empty list.
Line 21: The second case statement implements the general case. In our quicksort implementation, we always choose the head element of the list as the pivot. The function call smallerEq x xs returns the list containing elements smaller or equal to the element x. Similarly, the function greater x xs returns the list containing elements smaller or equal to the element x. We finally call our qsort function on these resulting lists and we assume our function correctly sorts both the lists. Lastly, we place the x element in between these sorted lists and concatenate the result to return the final list.

Free Resources

License: Creative Commons-Attribution-ShareAlike 4.0 (CC-BY-SA 4.0)