The Museum of HP Calculators

HP Forum Archive 17

[ Return to Index | Top of Index ]

RE: 35s sorting routine challenge - Gene's Challenge
Message #1 Posted by Miguel Toro on 29 July 2007, 4:02 p.m.

Hi,

This is an implementation of the "Insertion sort" algorithm. I find that it is reasonable fast and easy to program. This is my first try, but here it is for your consideration, though. It assumes that the numbers list begins always in register 0 and 10 items as the learning module, but it can be modified easily to follow Gene's requirements. I run it against the bubble program and it completed sorting in half the time or less. It was just fun to do it.

I001 LBL I
I002 1.009
I003 STO K
I004 RCL K
I005 STO I
I006 RCL (I)
I007 RCL I
I008 IP
I009 STO J
I010 x=0?
I011 GTO I022
I012 1
I013 -
I014 STO I
I015 x<>y
I016 RCL (I)
I017 x<=y?
I018 GTO I022
I019 STO (J)
I020 x<>I
I021 GTO I009
I022 x<>y
I023 STO (J)
I024 ISG K
I025 GTO I004
I026 RTN

LN=84 CK=AD7D

Regards,

Miguel

      
Re: RE: 35s sorting routine challenge - Gene's Challenge (EDITED!)
Message #2 Posted by Miguel Toro on 30 July 2007, 10:30 p.m.,
in response to message #1 by Miguel Toro

2007-08-01: PLEASE SEE BELOW FOR UPDATED ROUTINE. THANKS

This is the program modified so it can take a number X.YYYY as imput, specifying the first and last indirect registers of the list to be sorted.

I compared against the bubble sort, with a list of 100 elements and I got this results:

"insertion": 4 min. 26 sec.

"bubble": 16 min. 40 sec.

I think, it is not bad for a simple algorith. I'll work the program more to see if I can make it shorter and maybe faster. If someone could make a test run, I'd be happy to get comments.

Here it is (RLDN -> roll down):

I001 LBL I
I002 IP
I003 STO B
I004 LAST x
I005 STO K
I006 ISG K
I007 RCL K
I008 STO I
I009 RCL (I)
I010 RCL I
I011 IP
I012 STO J
I013 RCL B
I014 x=y?
I015 GTO I027
I016 RLDN
I017 1
I018 -
I019 STO I
I020 x<>y
I021 RCL (I)
I022 x<=y?
I023 GTO I028
I024 STO (J)
I025 x<>I
I026 GTO I012
I027 RLDN
I028 x<>y
I029 STO (J)
I030 ISG K
I031 GTO I007
I032 RTN

Regards,

Miguel

Edited: 1 Aug 2007, 8:46 a.m. after one or more responses were posted

            
Re: RE: 35s sorting routine challenge - Gene's Challenge
Message #3 Posted by Gene Wright on 31 July 2007, 12:09 a.m.,
in response to message #2 by Miguel Toro

Great job! This is the type of improvement I hope we see across the board.

It DOES make my initial sort routine in the learning module look really bad. :-)

                  
Re: RE: 35s sorting routine challenge - Gene's Challenge
Message #4 Posted by Miguel Toro on 31 July 2007, 12:01 p.m.,
in response to message #3 by Gene Wright

Thank you Gene!

It is really my pleasure and if one can make something more or less useful from time to time, that is a real satisfaction :-)

Regards,

Miguel

                  
Little change, big improvement
Message #5 Posted by Miguel Toro on 1 Aug 2007, 8:36 a.m.,
in response to message #3 by Gene Wright

How expensive a RCL is! I finally noticed that line I0010 is not necessary as written (duh myself), since I already have the value in the stack after line I008. So instead of RCL I, I use x<>y and voilą! 3min. 38sec. to sort 100 elements. This is 17% improvement in performance.

I001 LBL I
I002 IP
I003 STO B
I004 LAST x
I005 STO K
I006 ISG K
I007 RCL K
I008 STO I
I009 RCL (I)
I010 x<>y             -> RCL I becomes x<>y!
I011 IP
I012 STO J
I013 RCL B
I014 x=y?
I015 GTO I027
I016 RLDN
I017 1
I018 -
I019 STO I
I020 x<>y
I021 RCL (I)
I022 x<=y?
I023 GTO I028
I024 STO (J)
I025 x<>I
I026 GTO I012
I027 RLDN
I028 x<>y
I029 STO (J)
I030 ISG K
I031 GTO I007
I032 RTN

CK=11E4 LN=97

Miguel


[ Return to Index | Top of Index ]

Go back to the main exhibit hall