From: Jonathan duSaint <jdusaint@mathworks.com>
Newsgroups: comp.sys.hp48
Subject: insertion sort for the HP
Date: Thu, 30 Apr 1998 16:35:08 -0400
Organization: The MathWorks, Inc., Natick, MA 01760
Lines: 166
Message-ID: <3548E07C.FECB31BB@mathworks.com>
NNTP-Posting-Host: dusaint.mathworks.com
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
X-Mailer: Mozilla 4.04 [en] (WinNT; U)
Xref: republic.btigate.com comp.sys.hp48:10047

I've been working for a little while on an insertion sort routine for
the HP, and, after a few crashes and a lot of debugging, it's finally
ready to post, so here it is. For a rough test of its effiency, I timed
it against a quicksort routine that I have on my calculator (I don't
know the author) with the following results:

CPU speed = 3.92MHz, ROM Rev R
size   insertion   quick
2       .005       .005
5       .006       .008
10      .01        .011
50      .08        .05
100     .3         .1
500     7.9        .6
1000    31         1.3

Given the O(N^2) nature of the algorithm, these times aren't too bad. It
is interesting to note the large increase in time from 100 to 500. All
results were obtained using arrays produced by RANM.

So without further ado, here is the source code and the ASC code (and
I'm working on a base 64 encoder, so maybe I'll have to post that too
sometime).

The source code.
<------------- start cutting here --------------->
(Insertion sort for the HP48
 Adapted from the algorithm given in
 "Numerical Recipes in C"
 160.5 bytes, #897Dh
)
::
 CK1NoBlame
 CK&DISPATCH1 FOUR
 ::
  CKREF
  (make sure that the array has > 1 element)
  DUP ARSIZE #1= ?SEMI
CODE
	GOSBVL	=SAVPTR
	A=DAT1	A
	D1=A
	D1=D1+	5
	A=DAT1	A	* A[A] = length
	D1=D1+	10
	C=DAT1	A	* C[A] = number of dimensions
	B=C	A
	C=C+C	A
	C=C+C	A
	C=C+B	A	* multiply number of dimensions by 5

* by multiplying the number of dimensions by 5 and using that
* value for address calculation, it is possible to work with
* any dimension array

	A=A-C	A	* subtract that value from the length
	AD1EX
	A=A+C	A	* add it to the current D1
	AD1EX
	D1=D1+	5	* advance it to the start of the array proper
	LC(2)	15	* length still = length(els) + 15
	A=A-C	A
	CD1EX
	R2=C		* save address of start in R2
	A=A+C	A
	R4=A		* save address of end in R4
	C=0	A
	LC(2)	32
	A=A-C	A
	R3=A		* R3 -> second to last element

* the reason for keeping track of addresses is that this makes it
* unnecessary to keep any explicit counters which saves a great
* deal of calculation

* this is the start of the main loop
newel	SETDEC		* comparison subroutine requires DEC
	D1=A
	A=DAT1	W	* read in element to be inserted
	R0=A		* save it

search	D1=D1+	16	* point to next element
	AD1EX
	D1=A
	C=R4
	?A=C	A	* if pointing to end, insert
	GOYES	insert

	A=DAT1	W	* else read element in
	C=R0
	GOSUB	AgeC	* and compare
	GONC	search

insert	SETHEX		* this is where the actual insertion is done
	AD1EX		* this routine moves blocks at a time
	C=R3		* instead of one element at a time
	D1=C
	D0=C
	D0=D0+	16
	C=A-C	A
	C=C-CON	A,16	* create opening
	GOSBVL	=MOVEDOWN
	A=R0
	DAT1=A	W	* and insert element

	A=R3
	A=A-CON	A,16	* point to next element to be inserted
	R3=A
	C=R2
	?A>=C	A	* if pointing before start, all elements have been done
	GOYES	newel
	GOVLNG	=GETPTRLOOP

* AgeC (A>=C)
* I use this subroutine in place of TST15 in ROM because it compares
* nonsplit (12-form) reals instead of long reals.
AgeC	?A=C	S
	GOYES	sgnm	* if the sign is equal, then further tests are needed
	?A<C	S
	GOYES	sc
	RTNCC

sgnm	?A=C	X	* check the exponent
	GOYES	mnt
	B=C	X
	LC(3)	#499	* if they aren't equal, then denormalize them
	A=A+C	X
	C=B+C	X
	?A<C	X	* and compare again
	GOYES	alt
	GOTO	agt

mnt	?A=C	M	* if the exponents are equal,
	GOYES	sc	* then the mantissa is checked
	?A<C	M
	GOYES	alt

* these routines are used because if A>C and the sign nibble is 0,
* then the number in A is truly > the number in C, but if the sign
* nibble is 9, then the number in A is actually < the number in C

agt	?A=0	S
	GOYES	sc
	RTNCC
sc	RTNSC

alt	?A=0	S
	GOYES	cc
	RTNSC
cc	RTNCC
ENDCODE
 ;
;
<------------- stop cutting here ---------------->

The ASC code
<------------- start cutting here --------------->
%%HP T(3)A(R)F(.);
"D9D20D29512BF8171040D9D2044B7388130265307A226B3A16CCD20001008FB97601431311741431
79147D5C6C6C9EA133CA13317431F0EA13710ACA104D23102EA10305131153710017F13313111C8A
2011537118754053E0413311B13513416FEE818FAF8FC07601101517113818F8F10311A8BEC98D34
150942909C2130393291AB532994A3AA399B2916D00952E09D2B0948400302948400203B2130B213
0"
<------------- stop cutting here ---------------->

--Jon