Path: utzoo!utgpu!jarvis.csri.toronto.edu!cs.utexas.edu!usc!rutgers!att!drutx!druhi!neal
From: neal@druhi.ATT.COM (USENET News Administrator)
Newsgroups: comp.sys.handhelds
Subject: Fast sorting and re-ordering routines for HP-28S
Message-ID: <4533@druhi.ATT.COM>
Date: 1 Dec 89 18:53:34 GMT
Distribution: comp
Organization: AT&T Bell Labs, Denver CO
Lines: 35

I typed in the sort function from the reference manual and was very
disappointed with it.  First of all, it uses a bubble sort, which
may be the most overused bad example around.  As Knuth said in 1973,
"In short, the bubble sort seems to have nothing to recommend it, except
a catchy name and the fact that it leads to some interesting theoretical
problems."

Second, it operates on lists.  It seems that doing GETs from lists is
much slower than doing GETs from arrays.  Just changing the way that
the length of the input is calculated allows the same algorithm to run
much faster given an array as an argument.

I implemented an insertion sort algorithm which is faster still, especially
for data which is already nearly in order, but it still takes
around 2 minutes to sort 50 random numbers (without using FAST).

Another thing I want is a way to re-order whole arrays based on a
single column.  It might be best to generate the inversion of the
column and then make one pass through the array to re-order it.
Another possibility is to change the comparison method in the
sort program to be user-specified and sort a list of vectors (a taste
of object-oriented programming!  Too bad we can't overload primitive
operators like "<"...)

It would seem that a natural way to speed things up would be to develop
a machine-language implementation of the inner loop of the program.

Have any of these ideas been implemented and published?  I note that
EduCalc is listing a new book on tricks for the HP-28 which advertises
a sorting program.  Does anyone know if it is any good?

Thanks for any help!  If no one has a better solution, I'm willing to
post my insertion sort program.

-Neal McBurnett, neal@druhi.att.com or att!druhi!neal