Re: Quicksort (of a stack)

in reply to Quicksort (of a stack)
in thread Algorithm Pop Quiz: Sorting

Excellent. If you'll notice I *did* post a function (in PASM) that does a peek into the stack. The $2 question is, does the overhead of that function destroy the benefits of a quicksort? (I'll bet it does.) This is kinda cool though.

Comment on Re: Quicksort (of a stack)

Replies are listed 'Best First'.
Re: Re: Quicksort (of a stack) by robin (Chaplain) on Mar 26, 2002 at 13:10 UTC
Yeah I agree. I don't think it would be worth it. The quicksort should still be quicker than bubblesort most of the time - substantially quicker if there are a lot of elements to sort. If you do get this implemented in parrotcode, I'd be interested in seeing any benchmarks etc. It's an interesting curiosity that it's possible to do a sensible quicksort at all. I briefly considered using mergesort, but I don't think it can be done at all efficiently because there's only one stack.	[reply]

Replies are listed 'Best First'.

Re: Re: Quicksort (of a stack)
by robin (Chaplain) on Mar 26, 2002 at 13:10 UTC

The quicksort should still be quicker than bubblesort most of the time - substantially quicker if there are a lot of elements to sort. If you do get this implemented in parrotcode, I'd be interested in seeing any benchmarks etc.

It's an interesting curiosity that it's possible to do a sensible quicksort at all. I briefly considered using mergesort, but I don't think it can be done at all efficiently because there's only one stack.

[reply]

In Section Seekers of Perl Wisdom