[fpc-devel] Sorting tests

[J. Gareth Moreton]

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.

Kit

On 29/11/2022 08:22, Nikolay Nikolov via fpc-devel wrote:
>
> On 11/24/22 20:51, J. Gareth Moreton via fpc-devel wrote:
>> Hi everyone,
>>
>> I just need to touch on the knowledge base.  What tests exist that 
>> test the functionality of rtl/inc/sortbase.pp?  As Olly suggested, 
>> I'm looking at creating Introsort for this unit as well, but I need 
>> to know if such a unit already exists or if I need to make my own.
>
> But IntroSort is already implemented in 
> packages/rtl-extra/src/inc/sortalgs.pp. It's just not the default 
> sorting algorithm, because it breaks existing code that implements an 
> incorrect comparison function. E.g. if you pass a function that 
> returns a<b=true and b<a=true, or a<b=false and b<a=false, the 
> behavior will change, when you change the algorithm. This even broke 
> Lazarus, it caused it to hang on startup.
>
> Best regards,
>
> Nikolay
>
>>
>> Also, since Olly mentioned that the unit is used in TStringList, it 
>> makes me wonder if the RTL has a radix sort algorithm available, 
>> since radix sort is on the order of O(n) and is ideal for sorting 
>> large arrays of strings (although it can be memory-intensive).
>>
>> Kit
>>
>> _______________________________________________
>> 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
>