Haskell has a particularly elegant implementation of the quicksort algorithm:
qs :: (Ord a) => [a] -> [a] qs  =  qs (x:xs) = let smaller = qs [a | a <- xs, a <= x] bigger = qs [a | a <- xs, a > x] in smaller ++ [x] ++ bigger
This algorithm creates a new array that is sorted instead of sorting the given array in place. Therefore, there is no point in implementing a partitioning strategy (usually Hoare's).
qs :: (Ord a) => [a] -> [a]
This is just a type signature which can be read like this: "
qs is a function that takes an array of
as and produces a new array of
as where each element
a can be compared to another." The
(Ord a) part is a type constraint that means that
as need to be comparable, which makes sense since this is a sorting algorithm.
qs  =  qs (x:xs) = -- and so on...
let smaller = qs [a | a <- xs, a <= x] bigger = qs [a | a <- xs, a > x] in smaller ++ [x] ++ bigger
In Haskell, everything is an expression instead of a statement. Expressions are things that produce values. Statements are just lines of code that do something. Sometimes, it is useful to define intermediate values in an expression, and that is what the let block does. The result of the block is an array of
smaller ++ [x] ++ bigger.
[a | a <- xs, a <= x]
List comprehension generates lists (or arrays) using generators and guards (or filters). This code can be read "give me a list of
as where each
a is taken from the
xs list and is less than or equal to
x." (This is really just syntactic sugar on top of do notation, which itself is just syntactic sugar for monadic composition, but that's a topic for another time.)
xs.filter(s => s <= x). Arrow functions enable a relatively elegant alternative.
Here's the cool trick to put everything together: since there are only two branches of logic, the ternary operator provides a great mechanism for handling the conditions. We can use destructuring to split the array to its head and tail. Then we use the ternary operator to return an empty array if the head is undefined (since the array was empty), or the new array made up of the smaller array, current element, and bigger array. Here is the final code:
const qs = ([x, ...xs]) => x === undefined ?  : [ ...qs(xs.filter(s => s <= x)), x, ...qs(xs.filter(b => b > x)) ]
The coolest part of this implementation is that the whole thing is just an expression! There are no variable declarations at all (except the quicksort algorithm itself being assigned to a constant).
Amn3s1a2018 pointed out that my original code did not explicitly check for It's a cool refactor example, and its an example for a common error ... The updated version will still fail for arrays containing
x === undefined and would therefore fail for arrays including zeros.
The ternary operator nice replacement for the overload, but the correct way would
x !== undefined ? etc.
'cause this way qs filters out all falshy element from the array and drops there tail too.
undefined, but sorting such an array would be difficult because you would have to decide what to do with undefined values (probably remove them). Actually, if the array does not have
undefined as the first element, the filters will get rid of the rest of them and it will still work.
It's a cool refactor example, and its an example for a common error ...
The updated version will still fail for arrays containing
const qs = (arr) => [...arr].sort((a, b) => a - b);