In a functional language
Quicksort can be implemented in a wonderfully simple and elegant form:
qsort.hs
qsort [] = []
qsort (x:xs) = qsort lower ++ [x] ++ qsort higher
where
lower = filter (< x) xs
higher = filter (>= x) xs
If the beauty of this implementation doesn't "get" you - simply compare it with the
equivalent C code. There is no way you could call that either "simple" or "elegant"
although the underlying algorithm is!
But WAIT - it gets better! In a
lazy functional language finding the smallest element can now be implemented as:
> minimum = head . qsort
And because the sort is lazy this will take O(n) instead of the expected O(n log n)!
Ponder on that a moment before moving on...
Even better, we can find the
k smallest elements trivially:
> smallest k = take k . qsort
Once I wrapped my head around that I found it utterly
IN-CRE-DIBLE!
This code will only sort enough elements that are needed to take the smallest k.
Designing an elegant algorithim for efficiently finding the
k smallest elements has always bugged me. The superficial complexity of the sorting implementations always seemed to put me off. To do it in a single line (which is
working compilable code btw) is utterly mind-boggling.
This one line
automatically reduces to a
partition-based general selection algorithm with no additional complexity. Plus it works perfectly, is dead simple to maintain (what are the chances of introducing a bug in that single line?), and is (to me) very beautiful.
Note: If you have compilation problems with the above code due to the
monomorphism restriction add the following line:
> minimum :: (Ord a) => [a] -> a
