That is not a very good IntroSort to be honest. It is missing using
InsertionSort for small numbers and it does not do the median-of-3 pivot
selection.
Am 29.11.2022 um 09:22 schrieb Nikolay Nikolov via fpc-devel:
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
