# HP Forums

Full Version: HP 35s Gnome Sort
You're currently viewing a stripped down version of our content. View the full version with proper formatting.

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	RTN
LN=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.