[fpc-devel] Sorting tests
J. Gareth Moreton
gareth at moreton-family.com
Tue Nov 29 17:34:53 CET 2022
This is why I hope my own improvement to the version in TArrayHelper
could be used instead:
Now that I know where Introsort is in the sortalgs.pp unit, I'll see
about improving Introsort there too.
Regarding a stable sort, what does GCC's "std::stable_sort" use?
https://www.youtube.com/watch?v=kPRA0W1kECg&t=3m5s - it resembles merge
sort. (The algorithm before it in the video, "std::sort", is introsort,
but it postpones doing the insertion sort until the very end, which
doesn't work in practice because of caching issues)
On 29/11/2022 15:03, Stefan Glienke via fpc-devel wrote:
> 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,
>>> 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
> fpc-devel maillist - fpc-devel at lists.freepascal.org
More information about the fpc-devel