RE: List container strawman 1.2

["Steven Deller" <deller@smsail.com>]

> -----Original Message-----
> From: comp.lang.ada-admin@ada.eu.org 
> [mailto:comp.lang.ada-admin@ada.eu.org] On Behalf Of Ted Dennison
> Sent: Saturday, November 10, 2001 5:44 PM
> To: comp.lang.ada@ada.eu.org
> Subject: Re: List container strawman 1.2

> In article <3BED75C8.D9D55263@free.fr>, Jean-Marc Bourguet says...
> >A sorting algorithm is stable if after applying it, the 
> relative order 
> >of elements comparing equal is conserved.  That's useful 
> when you want
> 
> Well, that would clearly be up to the person who supplies the 
> comparison routine, would it not? I mean (assuming the 
> current definition), if "<" or ">" is supplied, then equal 
> values will not be changed. On the other hand, if "<=" or 
> ">=" are supplied, then they will be.

That is not true.  There is no comparison routine that can be supplied
in an instantiation that will convert a non-stable sort to a stable
sort.  It is necessary to "know" the original positions and include
those positions as part of the comparison (the original position becomes
the tie-breaker to keep equal values from switching places).

For any sort that is O(NlogN) in time, converting it to a stable sort
requires O(N) space (to keep the position values with the records).  One
of the better ways to do a stable sort on an array is to create an O(N)
list of pointers to the original elements, sort the pointers, and then
rearrange the original array to match the new positions of the pointers.
The position of the elements then becomes the "tie-breaker".

I'd prefer having a "stable sort" generic that "wraps" an arbitrary
generic sorting routine, but it is not possible to pass a generic as a
generic formal :-(.

Jean-Marc Bourguet has it pretty much right, though I would prefer a
heap sort instead of a merge sort.  A heap sort is also guaranteed
O(NlogN) time, and also can be done "in place" more easily.

Regards,
Steve Deller
Smooth Sailing LLC