The Quicksort Shootout
If you are interested in implementing quicksort in any reasonable language from scratch, you may not want to read this post.
I had some fun making this post but by all means draw your own conclusions and ignore my commentary.
The OO Languages
Io
List quicksort := method(
(self isEmpty) ifTrue(return List clone) ifFalse(
first := self first
rest := self slice(1)
below := Quicksort quicksort(rest select(i, i < first))
above := Quicksort quicksort(rest select(i, i >= first))
return below appendSeq(list(first) appendSeq(above))
)
)
I’ll be honest: this one took the longest and was the hardest to write. Additionally, it is the not very aesthetically pleasing (though moreso than any of the other OO languages), and I still don’t understand how Io knows when to execute a given piece of code (look at the select portion). It also was pretty unreadable until I separated the above and below variables out. I also didn’t understand why I needed return but it seemed to break the code to not have it there.
That said, it is very whitespacey, which is worth points in my book. This is the implementation I’m the least confident of. Io has changed a lot since I last was using it, and I never became very proficient at it.
Python
def quicksort(l):
if l == []:
return []
else:
x, xs = l[0], l[1:]
return quicksort([ i for i in xs if i < x ]) + \
[x] + quicksort([ i for i in xs if i >= x ])
For some reason, the list comprehensions didn’t do it for me this time. I preferred them in the functional languages where there seems to be less overhead. The parallel assignment helped a bit, but the lack of pattern matching was pretty annoying.
Ruby
def quicksort(l)
if l == [] then
[]
else
x, *xs = l
quicksort(xs.select { |i| i < x }) + [x] +
quicksort(xs.select { |i| i >= x })
end
end
It feels a little tidier than Python. The select was a little tidier than the equivalent list comprehension in Python, and seems to get right to the point a little better whereas with the list comprehension, the meaningful portion is in the if conditional on the far right.
I prefer the x, *xs = l notation, because it reminds me of pattern matching in the functional languages.
The Functional Languages
Haskell
module Quicksort where
quicksort (x:xs) = quicksort [ i | i <- xs, i < x ]
++ [x] ++
quicksort [ i | i <- xs, i >= x ]
quicksort [] = []
Well, you’d expect a winner, and lo, it is a winner.
Erlang
-module(quicksort).
-export([quicksort/1]).
quicksort([H|T]) ->
quicksort([ X || X <- T, X < H ])
++ [H] ++
quicksort([ X || X <- T, X >= H ]);
quicksort([]) -> [].
Looks just like the Haskell to me, albeit with Prolog-esque syntax. But I like Prolog, so that’s worth a couple points. :) Tie with Haskell.
OCaml
let rec quicksort = function
| (x::xs) ->
(quicksort (List.filter (fun i -> i < x) xs))
@ [x] @
(quicksort (List.filter (fun i -> i >= x) xs))
| [] -> []
;;
Naturally, a bit of OCaml noise enters the picture. No nice list comprehension syntax so we get to use the old-fashioned filter function. However, it’s still quite small. I think it is very readable, I’m just wondering whether OCaml is going to wind up being the functional language I use the least.
Lisp
(defun quicksort (l)
(cond
((null l) nil)
(t (let ((x (car l))
(xs (cdr l)))
(concatenate 'list
(quicksort (remove-if #'(lambda (i) (< x i)) xs))
(cons x nil)
(quicksort (remove-if #'(lambda (i) (> x i)) xs)))))))
Wow. That’s… so ugly. By far the wordiest functional language. I could have done it without the let block though, in which case it looks like this:
(defun quicksort (l)
(cond
((null l) nil)
(t (concatenate 'list
(quicksort (remove-if #'(lambda (i) (< (car l) i)) (cdr l)))
(cons (car l) nil)
(quicksort (remove-if #'(lambda (i) (> (car l) i)) (cdr l)))))))
How unpleasant. I would have expected Lisp to do better. Oh well.