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@lists.freepascal.org
https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
_______________________________________________
fpc-devel maillist - fpc-devel@lists.freepascal.org
https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
_______________________________________________
fpc-devel maillist - fpc-devel@lists.freepascal.org
https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
