alonzo@microsoft.UUCP (Alonzo GARIEPY) (03/28/90)
Here is yet another incarnation of quicksort for the HP 48.
This variation differs in that only one copy of each element
exists while the sort is taking place. All objects are kept
on the stack (as references) so that the memory overhead is
about 5 nibbles per element (2500 bytes for a 1000 element
list). This is most helpful when you are sorting large objects
or are low on memory.
It is possible to use less memory by sorting in place, but that
would be extremely slow because of list handling. Sorting with
an array of references is a typical way to avoid the cost of
copying data during a sort.
In one test, this sort took about 24 minutes for a list of 500
random real number. It could be made faster by eliminating one
or both of the temporary variables. The sort could be made
faster by replacing the code, 1 i START n ROLLD NEXT, with a
single machine code command. I'll see what I can do.
QSORT
%%HP: T(3)A(D)F(.);
\<<
LIST\-> \-> i
\<< i QST i \->LIST \>>
\>>
QST
%%HP: T(3)A(D)F(.);
\<<
IF DUP 2 <
THEN DROP
ELSE \-> n
\<< n 2 / ROLL n 3 + 2 n
START ROT 3 DUPN SWAP ROLLD > - NEXT
4 - -> i
\<< n ROLLD i QST 1 i START n ROLLD NEXT n i 1 + - QST \>>
\>>
END
\>>
Alonzo Gariepy
alonzo@microsoft