[fpc-devel] Sorting tests
J. Gareth Moreton
gareth at moreton-family.com
Tue Nov 29 10:09:45 CET 2022
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.
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,
>> 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).
>> fpc-devel maillist - fpc-devel at lists.freepascal.org
> fpc-devel maillist - fpc-devel at lists.freepascal.org
More information about the fpc-devel