Well, I decided to try my hand at something a bit more ambitious than my last little project (linear interpolation, released here to stunning, and yet oddly silent fanfair. I'm sure everyone was just over-awed and unable to comment. Yeah, that's the ticket).

I thought maybe a simple sort routine would be a good project. I did a search, and found a nice page on Wiki with all sorts of algorimthms, with a nice summary of speed, complexity, storage requirements, etc.

I selected the Gnome Sort, since it seemed to be the smallest, simplest. Pseudo-code follows:

void gnomesort(int n, int ar[])

{

int i = 0;while (i < n)

{

if (i == 0 || ar[i-1] <= ar[i])

i++;

else

{

int tmp = ar[i];

ar[i] = ar[i-1];

ar[--i] = tmp;

}

}

}

Couldn't be much simpler, right?

Well, as I set about transforming this simple, benign bit of C code into HP-calc-ese, with all it's GTO and lack of labelling capability glory, I quickly re-learned the lesson of why I haven't used a "goto" command in over two decades. Goto sucks.

I REALLY struggled to transform the if-then-else logic into goto-ese. It was made more complex because the operand of the if() statement is a compound statement with OR logic. I'm quite confident someone could turn that into something better than I came up with, I ended up kludging it together with several GTO statements and Flag 0.

For better or worse, here is the program. It is called assuming

bbb.eee

is in the X-stack, and will then gnome-Sort the contents of memory registers 'bbb' to 'eee', in ascending order. Note that it will not sort complex or vector contents.

Memory registers used: I, J, Y, Z

Flags used: 0

S001 LBL S

S002 INTG

S003 STO I

S004 STO Y first register to be sorted

S005 LASTX

S006 FP

S007 1000

S008 *

S009 STO Z last register to be sorted

S010 CF 0 start of while (I < n) loop

S011 RCL Y first register

S012 RCL I current register

S013 x == y? if(i==0)

S014 SF 0

S015 1

S016 -

S017 STO J

S018 RCL (I) ar[i]

S019 RCL (J) ar[i-1]

S020 x <= y? if(ar[i-1] <= ar[i])

S021 SF 0

S022 FS? 0 if ( (i==0) || (ar[i-1] <= ar[i]) )

S023 GTO S030

S024 STO (I) ar[i] = ar[i-1]

S025 RDN

S026 STO (J) ar[i-1] = ar[i]

S027 1

S028 STO- I i--;

S029 GTO S032

S030 1

S031 STO+ I i++;

S032 RCL Z

S033 RCL I

S034 X <= Y? while(i<n)

S035 GTO S010

S036 CF 0

S037 RTNLN=118 CK=B393

A useful little program to load a bbb.eee range of memory registers with random numbers is as shown:

A001 LBL A

A002 STO I

A003 RANDOM

A004 STO(I)

A005 ISG I

A006 GTO A003

A007 RTN

Some timings:

21 registers, 10.030: 33 seconds

21 registers, 10.030: 37 seconds

101 registers, 10.110: ~15 minutes

Clearly the advantage of this program is simplicity at the cost of run time, but given we are talking about a calculator without the ability to move software on/off electronically, simplicity becomes pretty important.

I may try a bubble sort, and if I get crazy, a heap sort.

*Edited: 14 Feb 2009, 12:06 a.m. *