go ahead... be a heretic 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.

Create A New User
Node Status?
node history
Node Type: note [id://154260]
help
Chatterbox?
What's the matter? Cat got your tongue?...

How do I use this? | Other CB clients
Other Users?
Others meditating upon the Monastery: (5)
As of 2018-03-24 14:19 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
When I think of a mole I think of:

Results (298 votes). Check out past polls.

Notices?