RPN Stack Sort Problem « Next Oldest | Next Newest »

 ▼ Katie Wasserman Unregistered Posts: 1,477 Threads: 71 Joined: Jan 2005 07-25-2006, 02:00 AM 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 ▼ Paul Dale Unregistered Posts: 3,229 Threads: 42 Joined: Jul 2006 07-25-2006, 02:27 AM 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 ▼ Katie Wasserman Unregistered Posts: 1,477 Threads: 71 Joined: Jan 2005 07-25-2006, 03:27 AM 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. ▼ Paul Dale Unregistered Posts: 3,229 Threads: 42 Joined: Jul 2006 07-25-2006, 04:09 AM 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 ▼ Katie Wasserman Unregistered Posts: 1,477 Threads: 71 Joined: Jan 2005 07-25-2006, 10:02 AM 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. Paul Dale Unregistered Posts: 3,229 Threads: 42 Joined: Jul 2006 07-25-2006, 06:54 PM 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. ▼ Katie Wasserman Unregistered Posts: 1,477 Threads: 71 Joined: Jan 2005 07-25-2006, 09:08 PM Assuming a preloaded index counter is cheating! If you assume that X > Y then you can save 2 steps too :) ▼ Paul Dale Unregistered Posts: 3,229 Threads: 42 Joined: Jul 2006 07-26-2006, 12:00 AM 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 hal Unregistered Posts: 130 Threads: 36 Joined: Jan 1970 07-25-2006, 01:19 PM 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 Valentin Albillo Unregistered Posts: 1,755 Threads: 112 Joined: Jan 2005 07-25-2006, 04:13 AM 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. ▼ Katie Wasserman Unregistered Posts: 1,477 Threads: 71 Joined: Jan 2005 07-25-2006, 09:39 AM Right, I meant roll-up. Thanks for catching that! Katie Wasserman Unregistered Posts: 1,477 Threads: 71 Joined: Jan 2005 07-25-2006, 09:49 AM I just found John Dearing's "Stack Sort" for the 41C. It's more than 30 steps! This wheel could use some reinventing. :) ▼ Ed Look Unregistered Posts: 801 Threads: 36 Joined: Nov 2005 07-25-2006, 11:45 AM 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. ▼ Katie Wasserman Unregistered Posts: 1,477 Threads: 71 Joined: Jan 2005 07-25-2006, 12:21 PM 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. Ángel Martin Unregistered Posts: 1,253 Threads: 117 Joined: Nov 2005 07-26-2006, 04:41 AM I know it's cheating but... it takes just *one* step on the 41C, using my SandMath ROM (or the SandBox): STSORT Best, ÁM ▼ Paul Dale Unregistered Posts: 3,229 Threads: 42 Joined: Jul 2006 07-26-2006, 07:20 PM 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 2,649 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 2,224 11-19-2013, 08:59 AM Last Post: Miguel Toro emu48 - copy stack doesn't work (as expected) Thomas Radtke 2 1,945 11-11-2013, 02:19 PM Last Post: Thomas Radtke HP Prime Stack operations from within a program John Colvin 1 1,352 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 2,438 11-05-2013, 02:44 AM Last Post: Marcus von Cube, Germany PRIME Spreadsheet RPN Problem Dougggg 5 2,479 10-24-2013, 11:46 PM Last Post: Han Prime: Anyway to refresh stack? kris223 5 2,096 10-16-2013, 05:09 PM Last Post: kris223 hp prime - sending program results to the stack giancarlo 6 2,064 10-15-2013, 02:00 AM Last Post: Giancarlo Rearanging the "Fixed" sort order of Prime's Apps icons Joe Horn 3 1,682 10-02-2013, 10:24 AM Last Post: Han HP Prime - RPN stack access from programs? Mike Mander (Canada) 10 3,346 09-30-2013, 11:20 AM Last Post: steindid

Forum Jump: