Willie Wheeler's personal blog. Mostly tech.
I just ran across the following Haskell quicksort implementation, courtesy of Wikibooks:
qsort  =  qsort (x:xs) = qsort (filter (<= x) xs) ++ [x] ++ qsort (filter (> x) xs)
This recursive definition is dense but easy to follow. The first line is the base case. In the second line,
x is the first element and
xs is the rest of the list. Using
x as the pivot, we concatenate the sorted lower elements, the pivot and the sorted higher elements.
Here it is in action:
ghci> qsort [9,22,1,23,0,-12,3,44,5,4,5,2,44,3,14,15,23] [-12,0,1,2,3,3,4,5,5,9,14,15,22,23,23,44,44]
To be sure, this isn't an optimized implementation. For example, it doesn't choose either a central or a random pivot, so it performs poorly with lists that are already sorted. And it does two passes through the
xs at each recursion instead of one.
Still, it's pretty great how the tiny but dense code "captures" quicksort. It's eye-opening to compare it to implementations in other languages.