The Museum of HP Calculators

HP Forum Archive 17

 RE: 35s sorting routine challenge - Gene's ChallengeMessage #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 ChallengeMessage #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 ChallengeMessage #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 improvementMessage #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

Go back to the main exhibit hall