Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!cs.utexas.edu!rutgers!att!drutx!druhi!neal
From: neal@druhi.ATT.COM (Neal D. McBurnett)
Newsgroups: comp.sys.handhelds
Subject: Re: Fast sorting and re-ordering routines for HP-28S
Message-ID: <4538@druhi.ATT.COM>
Date: 5 Dec 89 15:29:13 GMT
References: <553@kunivv1.sci.kun.nl>
Distribution: comp
Organization: AT&T Bell Labs, Denver CO
Lines: 34

in article <553@kunivv1.sci.kun.nl>, ge@kunivv1.sci.kun.nl (Ge' Weijers) says:
> Well, insertion sort is only better than bubble sort by a constant factor.

Thanks for the correction of any misperception I might have spread.
I realize that for big sorting tasks one clearly wants an algorithm
better than O(N^2) (both bubble and insertion sorts are O(N^2)).

On the other hand, it is important to tailor a sorting algorithm to the
hardware and application at hand.  If we are interested in getting
a routine which can quickly sort 10 or 20 numbers we will be less interested
in the n^2 term than in the constant factor.  If we want to sort 100
numbers we are much more interested in the n^2 term.

If we're sorting large arrays it is also desireable to do the sorting
in place, and avoid having to use a lot of extra memory.

After some more thought, I have concluded
that there are at least two promising avenues for the HP28 architecture.
One is to take advantage of the "sigmaMAX" or "sigmaMIN" operation and
implement a selection sort.  Unfortunately, the POS function doesn't
work on arrays, and sigmaMIN doesn't work on lists.  What a shame.  It
may make sense to keep two copies of the data, one in an array for finding
the minimum value, and one in a list for finding out where that minumum
value is.

The other idea is to do the sorting on the stack.  It seems that
ROLL on the stack is faster than a PUT into an array even for a set of data
100 elements long.

If I were to choose a good algorithm for a large array, it would
probably be one of heapsort, quicksort or shell's sort, depending on
which one was easiest to implement.

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