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



#2

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


#3

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


#4

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


#5

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

#6

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


Possibly Related Threads...
Thread Author Replies Views Last Post
  HHC 2013 RPN Programming Challenge - Final Thought Jeff O. 7 392 10-17-2013, 11:02 AM
Last Post: Jeff O.
  Challenge(?): Intersection curve between two cylinders in a specific position Pier Aiello 15 612 09-17-2013, 05:58 PM
Last Post: Pier Aiello
  WP-34S Matrix operations with routine-local registers? Tom Grydeland 1 185 09-04-2013, 10:46 AM
Last Post: Marcus von Cube, Germany
  Advantage/CCD Matrix Challenge Ángel Martin 1 178 08-09-2013, 06:22 PM
Last Post: Thomas Klemm
  SandMath routine of the week: Inverse Gamma Function Ángel Martin 39 1,368 03-24-2013, 08:19 AM
Last Post: peacecalc
  My birthday, so a little commemorative mini-challenge ! Valentin Albillo 43 1,490 03-07-2013, 03:44 AM
Last Post: Walter B
  41CL Routine of the Week - DLD48 Ángel Martin 1 164 02-15-2013, 08:30 PM
Last Post: Michael Lopez
  Math Challenge I could not solve Meindert Kuipers 22 934 01-05-2013, 04:43 PM
Last Post: Thomas Klemm
  WP 34S mini-challenge (B) Gerson W. Barbosa 17 654 12-27-2012, 04:39 PM
Last Post: Marcus von Cube, Germany
  41-CL Routine of the week: MMUSWAP Ángel Martin 3 240 11-09-2012, 01:39 PM
Last Post: Luiz C. Vieira (Brazil)

Forum Jump: