[fpc-devel] Sorting tests

[Sven Barth]

Ondrej Pokorny via fpc-devel <fpc-devel at lists.freepascal.org> schrieb am
Di., 29. Nov. 2022, 11:39:

> Am 29.11.2022 um 11:08 schrieb Sven Barth via fpc-devel:
>
> J. Gareth Moreton via fpc-devel <fpc-devel at lists.freepascal.org> schrieb
> am Di., 29. Nov. 2022, 10:09:
>
>> Surely that's a bug in the comparison functions that should be fixed and
>> not something that can be blamed on introsort.  If a comparison function
>> is faulty, then pretty nuch any sorting algorithm can be considered to
>> have unpredictable behaviour.
>>
>
> This *can* be blamed on IntroSort, because Stability (order of equal
> elements is kept) is an attribute of sorting algorithms and IntroSort is
> *not* considered stable while QuickSort *can* be stable depending on the
> implementation and ours *is*.
>
> If for two elements [a, b] the comparison function returns
> a<b=true and b<a=true
>
> then the problem is not in stability or any other feature of the sorting
> algorithm but in the comparison function indeed. Or am I missing something?
>

For such a comparison function the issue is indeed in the comparison
function, but Nikolay also mentioned "a<b=false and b<a=false" which is the
case for equal elements.

Regards,
Sven

>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.freepascal.org/pipermail/fpc-devel/attachments/20221129/c2771a37/attachment.htm>