RPN Stack Sort Problem



#2

Here's a little RPN stack manipulation problem/challenge:

What's the least number of instruction steps needed to sort the stack? Specifically, given random values in X, Y, Z and T arrange them in order with the largest value in X, next largest in Y, etc..

I can't find a solution better than the obvious one (you can figure that out for yourself) that takes 20 steps on a 12C -- a couple less on RPN calculators that have a roll-up [edited] function and/or subroutines. There must be some clever way to do this, but I'm stumped.

Edited: 25 July 2006, 2:20 p.m. after one or more responses were posted


#3

I've not tried any of this on a calculator yet so forgive any obvious errors.

If we bubble sort the stack we basically need to do the following sequence lots of times:

    x <= y?    comparison (x < y? avoids unnecessary swaps)
x <> y swap x & y
Rv roll down

The first pass over the stack (repeating this sequence three times, followed by one Rv) puts the largest value into the t register and maybe juggles the others. The second pass only needs this sequence twice with two Rv to bring the stack back to its original position. The third and final pass only needs the sequence once and either three Rv or one R^. So 24 steps on a 12c and 22 steps on a machine with roll up.

Can we do better? Of course:

    STO I
Rv
1
2
x <> I
LBL 0
x <= y?
SWAP
Rv
DSE I
GTO 0

A total of 11 steps. This skips the extra Rv's from above and replaces them with the three instruction test, swap and roll down sequence which is harmless. Do this sequence a dozen times and the stack will be sorted.


- Pauli


#4

Bubble sort is the obvious method but your code doesn't work because it treats the stack as a circular list. Taking care of this problem is what complicates the coding in a loop and the straight line code is what takes 20 steps (not 24) on a 12C.


#5

I figured out it had a problem soon after posting. I really should have tried it out first :-(

I need to execute the trio of compares then a Rv and do that lot thrice. On a 32sii I get this program:

    LBL A
X <> K
STO I
X <> K
LBL B
X <> K
STO J
X <> K
LBL C
x < y?
x <> y
Rv
DSE J
GTO C
Rv
DSE I
GTO B

Assuming that register K contains the value 3.

17 steps in all. Plus you might be able to ditch the two "x <> K" when setting up I.


- Pauli


#6

Pauli, that looks a lot better! I found a few different 17 step solutions I found when using something better than a 12C. But all of them are just variations of bubble sort. I wonder if there's some totally different way to do this, maybe using some arithmetic tricks?

The 6 comparisons needed by bubble sort is the theoretical minimum for a 4 element sort. Given that all the RPN calculators (I think) only allow for comparing X and Y there's a good amount of stack manipulation is going to be needed. So probably the only way to do better than 17-20 steps is to employ some trick or make use of some not-at-all-obvious calculator function.

#7

Better is:

    3
STO I
...
LBL 0
x < y?
x <> y
Rv
x < y?
x <> y
Rv
x < y?
x <> y
Rv
Rv
DSE I
GTO 0

This unrolls the inner loop at no cost in space and a good speed improvement.

15 steps so long as I can initialise the index register ahead of time.


- Pauli

Edited: 25 July 2006, 6:59 p.m.


#8

Assuming a preloaded index counter is cheating! If you assume that X > Y then you can save 2 steps too :)


#9

Oh well...

I figured loading the 3 into I before stacking the satck wasn't totally unreasonable. At least I did count the two steps for loading it.

If you've got a 3 stashed in another register (say 0) you can do it in three steps

    X<>0, STO I, X<>0

If that isn't allowed, I can do it in four steps:

    STO I, Rv, 3, x<>I

Another way to do it in 4 steps:

    STO I, STO+ I, STO+ I, STO/ I


- Pauli

#10

Quote:
The first pass over the stack (repeating this sequence three times, followed by one Rv) puts the largest value into the t register and maybe juggles the others. The second pass only needs this sequence twice with two Rv to bring the stack back to its original position. The third and final pass only needs the sequence once and either three Rv or one R^. So 24 steps on a 12c and 22 steps on a machine with roll up.





I don't see that you need a roll up / down command after the third pass through. I got 20 steps (excluding the label) for a simple bubble routine using only roll downs.

best regards, Hal
#11

Hi, Katie:

Katie posted:

"I can't find a solution better than the obvious one (you can figure that out for yourself) that takes 20 steps on a 12C -- a couple less on RPN calculators that have a
roll-down function and/or subroutines."

    You mean roll-up, right ? Because all my three HP-12C's do have a roll-down function right on the keyboard. :-)

    Also, I'm pretty sure this particular stack sorting routine you're interested in was probably covered in some old PPC Journal issues, or perhaps in the excellent "Calculator Tips & Routines" by John Dearing.
    It would be probably wise to look for it in this last reference first, before wasting too much time allegedly trying to reinvent the wheel.

Best regards from V.

#12

Right, I meant roll-up. Thanks for catching that!

#13

I just found John Dearing's "Stack Sort" for the 41C. It's more than 30 steps! This wheel could use some reinventing. :)


#14

I am not much of a programmer, nor am I super-adept in mathematics. I once asked someone, I think in this very forum, for a method to sort roughly thirty values in a HP-33S, or any other four-level stack RPN machine.

Needless to say, I forgot it, but I do recall it required many steps, not seventeen or twenty-five.

If I may ask, how would you sort a larger number of values than stack levels available... COMPLICATED by the fact that the 33S has twenty-six (and a half?) data registers and older beauties, like the 34C, have a few less?

I'm sure I can kluge up some way of doing it, but taking a year and three quarters and almost filling its programming memory is not a good way to do it.


#15

You can program a simple bubble sort on any HP calculator that allows indirect register addressing. Even the lowly 12C can do it, and in not very many steps:
12C bubble sort

Bubble sorting 26 data elements isn't that time consuming on a 33S (30 elements would be hard on this calculator because the 27'th register is the index register needed for indirect addressing), but running time is proportional to the square of the number of data elements so you probably would want to use a better sorting algorithm on a calculator capable of addressing more registers. There are a vast number of sorting algorithms the best of which is
Quicksort in most cases.

#16

I know it's cheating but... it takes just *one* step on the 41C, using my SandMath ROM (or the SandBox):

STSORT

Best,
ÁM


#17

It is pretty easy on a HP49g+ too:

<< DEPTH ->LIST SORT LIST-> DROP >>


- Pauli


Possibly Related Threads...
Thread Author Replies Views Last Post
  HP 50g - select characters on the stack, copy/paste Sean Freeman 7 1,934 11-20-2013, 07:11 AM
Last Post: Sean Freeman
  Prime: Placing more than 1 item on the RPN stack in a single program? John Colvin 4 1,591 11-19-2013, 08:59 AM
Last Post: Miguel Toro
  emu48 - copy stack doesn't work (as expected) Thomas Radtke 2 1,495 11-11-2013, 02:19 PM
Last Post: Thomas Radtke
  HP Prime Stack operations from within a program John Colvin 1 1,009 11-08-2013, 09:45 PM
Last Post: Helge Gabert
  [PRIME] RPN: another attempt at returning more than one value to the RPN stack Marcus von Cube, Germany 5 1,825 11-05-2013, 02:44 AM
Last Post: Marcus von Cube, Germany
  PRIME Spreadsheet RPN Problem Dougggg 5 1,805 10-24-2013, 11:46 PM
Last Post: Han
  Prime: Anyway to refresh stack? kris223 5 1,620 10-16-2013, 05:09 PM
Last Post: kris223
  hp prime - sending program results to the stack giancarlo 6 1,510 10-15-2013, 02:00 AM
Last Post: Giancarlo
  Rearanging the "Fixed" sort order of Prime's Apps icons Joe Horn 3 1,237 10-02-2013, 10:24 AM
Last Post: Han
  HP Prime - RPN stack access from programs? Mike Mander (Canada) 10 2,501 09-30-2013, 11:20 AM
Last Post: steindid

Forum Jump: