Warp wrote:

>   I think he has a point. Quicksort is not such a good example because
> quicksort is rather easy and short to implement in almost any language
> (which is one of the strengths of quicksort: it's so fast because its
> inner loop is so small).

I think he has a point too.

However, as the blog author points out, it's kinda difficult. To see how 
good a language "really is", you need a non-trivial example. But if 
you're trying to write a tutorial, you need small examples which are 
easy to understand - in other words, trivial. Kind of a no-win situation 
there...

>   What I would like to see is introsort in haskell to see how easy and
> fast it is.

Heh. I once tried to implement something similar to this. It did an 
insert sort on lists of less than 50 elements, and a quicksort 
otherwise. However, I made a *fatal* mistake: I used the "length" 
function to determine the size of the list. At every iteration.

Shall we just say it was "not fast"?

Anyway, assuming you've already got a heapsort function that takes a 
list and completely sorts it, and you want to swap from quicksort to 
heapsort after exactly 16 iterations, you could do something like this:

   introsort = choose 16

   choose 0 xs = heapsort xs
   choose n (x:xs) =
     (choose (n-1) (filter (<x) xs)) ++ [x] ++
     (choose (n-1) (filter (>x) xs))

Of course, a good quicksort utterly depends on picking the right pivot. 
And for a linked list, it seems hard to do that without wasting too much 
time trying to pick a pivot. So I'm not really sure quicksort is a good 
algorithm to be using on a linked list in the first place, but hey...

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message