[fpc-devel] Sorting tests
sglienke at dsharp.org
Tue Nov 29 16:06:56 CET 2022
More like a variation of that: TimSort - but that's rather a beast to
implement properly and efficient.
Am 29.11.2022 um 14:41 schrieb J. Gareth Moreton via fpc-devel:
> Quicksort is not inherently stable because of what happens if a value
> is equal to the pivot - more specifically, which of the identical
> values is selected as the pivot - for example, if you try to sort a
> list of identical values, they will inevitably change order because
> each stage will move all of the values to one side of the pivot (and
> also cause quicksort to degenerate into O(n²)). If you want a stable
> sort, you need to use things like merge sort instead.
> On 29/11/2022 13:25, Sven Barth via fpc-devel wrote:
>> 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.
>> fpc-devel maillist -fpc-devel at lists.freepascal.org
> fpc-devel maillist -fpc-devel at lists.freepascal.org
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the fpc-devel