[fpc-devel] Sorting tests

[Stefan Glienke]

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.
>
> Kit
>
> 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.
>>
>> Regards,
>> Sven
>>
>>
>> _______________________________________________
>> fpc-devel maillist  -fpc-devel at lists.freepascal.org
>> https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
>
> _______________________________________________
> fpc-devel maillist  -fpc-devel at lists.freepascal.org
> https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.freepascal.org/pipermail/fpc-devel/attachments/20221129/00a7ef2a/attachment.htm>