Beefy Boxes and Bandwidth Generously Provided by pair Networks
go ahead... be a heretic
 
PerlMonks  

Re: Quicksort (of a stack)

by clintp (Curate)
on Mar 26, 2002 at 12:58 UTC ( #154384=note: print w/ replies, xml ) Need Help??


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.

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://154384]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others surveying the Monastery: (11)
As of 2015-07-07 20:46 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The top three priorities of my open tasks are (in descending order of likelihood to be worked on) ...









    Results (93 votes), past polls