Beefy Boxes and Bandwidth Generously Provided by pair Networks
Syntactic Confectionery Delight
 
PerlMonks  

Re: Algorithm Pop Quiz: Sorting

by clintp (Curate)
on Mar 25, 2002 at 22:55 UTC ( #154260=note: print w/ replies, xml ) Need Help??


in reply to Algorithm Pop Quiz: Sorting

Okay, here's my solution and it's -- horror of horrors -- a classic bubble sort. Since I had already implemented PEEK and REPLACE (for other things I needed) writing a simple bubble sort wasn't too much of a bother.

Everyone seemed to do the same sort of modified bubble sort, but they're more efficient than mine being self-contained and not requiring SWAP and PEEK. With no objections I'd like to borrow the general algorithm for an OSS project -- this PerlMonks thread cited.

Unless something frighteningly better comes along.

# Stack Library # This'll get a whole lot cleaner when I can tell the # depth of the stack automagically # peek -- return whatever string is on the stack # Inputs: the offset on the stack # Outputs: the string # Non-Destructive! # Does *not* test for bounds conditions PEEK: pushi restore I0 set I3, I0 inc I0 set I2 0 PLOOP: ge I2, I3, POL rotate_up I0 inc I2 branch PLOOP POL: restore S0 save S0 eq I0, 0, EOP rotate_up I0 EOP: save S0 popi ret # REPLACE -- replace thing at stack position X # Inputs: the offset to remove # the string to leave in its place # Outputs: The string removed # Note: Almost *identical* to PEEK above # Does *not* test for bounds conditions REPLACE: pushi pushs restore S1 restore I0 set I3, I0 inc I0 set I2, 0 RLOOP: ge I2, I3, ROL rotate_up I0 inc I2 branch RLOOP ROL: restore S0 save S1 eq I0, 0, ENDOFREPLACE rotate_up I0 ENDOFREPLACE: save S0 popi pops ret # swap -- swap the position of two strings on the stack # Inputs: Offsets of the two things on the stack # Outputs: None. # Does *not* test for bounds conditions SWAP: pushi pushs restore I0 restore I1 save I0 save "-" # Just a dummy bsr REPLACE restore S0 save I1 save S0 bsr REPLACE restore S1 save I0 save S1 bsr REPLACE restore S1 # dummy popi pops ret # Sort whatever's on the stack. # Yes, this is a bubble sort. Get over it. # Inputs: Stack depth on top of the stack # Outputs: Stack depth on top of the stack SORTSTACK: pushi pushs restore I5 set I0, 0 set I1, 0 BUBBLE: inc I1 le I1, I0, BUB1 set I1, 0 inc I0 BUB1: ge I0, I5, SORTEND save I1 bsr PEEK restore S2 save I0 bsr PEEK restore S3 le S2, S3, BUBBLE save I1 save I0 bsr SWAP branch BUBBLE SORTEND: save I5 popi pops ret
What? You expected me to post Perl code? :)

Now, can you write me a general purpose expression evaluator given just the tokens on the stack? and...oh nevermind.


Comment on Re: Algorithm Pop Quiz: Sorting
Download Code

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others examining the Monastery: (4)
As of 2014-09-21 22:01 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    How do you remember the number of days in each month?











    Results (176 votes), past polls