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.