🚀 go-pugleaf

thads@csn.net (Thad Smith) writes:
	...
>>>What do you do if you need a stable sorter?  Or what does Num Rec.
	...
>>You take the index into account in your comparison function, as a
>>"secondary key", if the items being sorted are otherwise equal.
>...
>>int stablecompare(void *a, void *b)
>>{
>>    if(int comparison=gencompare(a,b)) return comparison;
>>    return (a<b)?-1:(a>b)?1:0;
>>}

>This does not work with most partitioned sorts, except merge sort

Oops -- perfectly right -- you need to take the _original_ index
of the item into account, not just wherever it happens to have
been shunted at present by the shuffling!  Recording original
indices will take another O(N) memory, and will transform the
stablecompare() into:

int stablecompare(void *a, void *b)
{
    int orga=original_index(a);
    int orgb=original_index(b);
    if(int comparison=gencompare(a,b)) return comparison;
    return (orga<orgb)?-1:(orga>orgb)?1:0;
}

To be able to write the crucial "int original_index(void *)" function
at all, of course, objects being sorted need to have SOME sort of
unique identifier; if they can be totally undistinguishable, this
approach cannot work (but then, if they're TOTALLY undistinguishable,
how is anybody ever to be going to tell that your sort is not stable?-).

Conceptually it's a mapping (void*)->object's unique identifier->int,
where the first '->' depends on the objects' exact nature, the
second one is built up as we go along -- if there's an OID->int entry
already for whatever OID we're dealing with, the int is returned,
else the int is computed from the (void*) knowing that the object
has not been moved yet (this relies on the underlying sort algorithm
never moving items before comparing them with something...).

In practice, this is likely to be only usable if the objects being
sorted have a "spare" data field that can be used to record the
original index of each object in a single pass before sorting
starts... otherwise, using a different algorithm appears to be
generally simpler.


Alex
--
DISCLAIMER: these are TOTALLY personal opinions and viewpoints, NOT connected
in any way with my employer, nor any other organization or individual!
Email: martelli@cadlab.it                            Phone: +39 (51) 597313
CAD.LAB s.p.a., v. Ronzani 7/29, Casalecchio, Italia   Fax: +39 (51) 597120