[fpc-devel] Sorting tests
nickysn at gmail.com
Tue Nov 29 09:22:18 CET 2022
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.
> 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
More information about the fpc-devel