Functional Snippet #3: Functional Quicksort

The following variant of Quicksort will definitely not win any speed price. Most real implementations of Quicksort will use constant memory. This snippet, however, is one of the shortest and clearest ways to write Quicksort:

func qsort(input: [Int]) -> [Int] {
    if let (pivot, rest) = input.decompose {
        let lesser = rest.filter { $0 < pivot }
        let greater = rest.filter { $0 >= pivot }
        return qsort(lesser) + [pivot] + qsort(greater)
    } else {
        return []

It builds on the decompose snippet: if the array is not empty, it uses the first element as the pivot, and seperates the array into two new arrays: the first containing only smaller elements, and the second containing only larger (or equal) elements. Then it sorts the smaller elements, appends the pivot element, and finally appends the sorted larger elements.

Stay up-to-date with our newsletter or follow us on Twitter.

Back to the Blog

recent posts