After a long Easter holiday filled with late night coding sessions I find myself wide awake at 2am… good job I’ve still got my pluralsight subscription and a quick look at the Algorithms and Data Structures course again at least gave me something to do to relax the mind with some back-to-school style implementation of common sorting algorithms in F#:
Whilst not the most performant implementations I’m sure, I hope at least it goes to show how easily and concisely these simple algorithms can be expressed in F#! Now back to that sleep thing…
Nice but I think Quicksort should use in-place partition in accordance with Hoare’s explanation in his original Quicksort paper otherwise you’ve taken the “quick” out of “quicksort”.
@Jon Harrop – thanks, you’re absolutely right, I’ve gone back and added the in-place version of quick sort now as well.
For an array of 1 million elements [| 1000000..-1..1 |], the simple version fails with OutOfMemoryException after quite some time, but the in-place version takes under 3 seconds to execute on my machine. When marked with inline (final version above) the same array takes around 150ms to run – a marked improvement!
That said, the built-in Array.sort function manages to sort the same 1-million element array in around 40ms, pretty impressive :-)