RE: 35s sorting routine challenge - Gene's Challenge

[Miguel Toro]

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

[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

[Gene Wright]

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. :-)

[Miguel Toro]

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

[Miguel Toro]

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