Re: [fpc-devel] Sorting tests
On 11/30/22 08:30, Nikolay Nikolov wrote: On 11/30/22 01:57, J. Gareth Moreton via fpc-devel wrote: Familarity mostly. More people are familiar with quicksort than introsort. Are there any explicit code examples where quicksort succeeds and introsort fails? I'm told even Lazarus crashes (or used to crash), so I'll be interested to see what code causes (or caused) it. IIRC, Lazarus had a comparison function that returned a Sorry, I meant to say ahttps://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
Re: [fpc-devel] Sorting tests
On 11/30/22 01:57, J. Gareth Moreton via fpc-devel wrote: Familarity mostly. More people are familiar with quicksort than introsort. Are there any explicit code examples where quicksort succeeds and introsort fails? I'm told even Lazarus crashes (or used to crash), so I'll be interested to see what code causes (or caused) it. IIRC, Lazarus had a comparison function that returned acaused an infinite loop, not a crash. I don't remember the details, you should examine the source control history. The problem was fixed a long time ago in Lazarus, however it was decided not to change the default algorithm, but rather provide a plugable mechanism for changing the algorithm, hence the sortalgs unit provides several different options. FPC developers didn't want to have the bug tracker be filled with bug reports, caused by that (people would first assume it's a bug in the new FPC version if their code fails on a new FPC version, but works in the previous version). Nikolay ___ fpc-devel maillist - fpc-devel@lists.freepascal.org https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
Re: [fpc-devel] Sorting tests
On Tue, 29 Nov 2022 23:57:14 + "J. Gareth Moreton via fpc-devel" wrote: > Familarity mostly. More people are familiar with quicksort than > introsort. Are there any explicit code examples where quicksort > succeeds and introsort fails? I'm told even Lazarus crashes (or used > to crash), so I'll be interested to see what code causes (or caused) > it. +1 >[...] Mattias ___ fpc-devel maillist - fpc-devel@lists.freepascal.org https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
Re: [fpc-devel] Sorting tests
Familarity mostly. More people are familiar with quicksort than introsort. Are there any explicit code examples where quicksort succeeds and introsort fails? I'm told even Lazarus crashes (or used to crash), so I'll be interested to see what code causes (or caused) it. If the pivot is one of the values with a duplicate key, then there is a chance that the other identical values will change order, and I don't think there's a fast away to avoid this situation. But if needs be, here's a worked example to show quicksort is not stable, say our data is: 3 2 1 4a 4b 4c 7 5 6 Choosing the median of three gives us 4b. Assuming we're using an "(a < b) = True" comparison to put items into the left partition: [3 2 1 *4b* 4a 4c 7 5 6] Recursing: [1 *2* 3] 4b [4a 4c 5 *6* 7] 1 2 3 4b [*4c* 4a 5] 6 7 (The pivot choice here depends on the order of checking the three values... here it's doing "l < m" (False), "m < r" (True) then "l < r" (True)) 1 2 3 4b 4c 4a 5 6 7 Thus, the middle items are not in the same order. Kit On 29/11/2022 22:58, Mattias Gaertner via fpc-devel wrote: On Tue, 29 Nov 2022 15:54:03 +0100 Benito van der Zander via fpc-devel wrote: Hi, and the FPC implementation is actually documented to not be stable in [...] and one can see that it is indeed not stable, if you sort ['a','b','A'] case-insensitively, it becomes ['A', 'a','b'] If the current QuickSort is not stable, is there an another argument for keeping it as default? Mattias ___ 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
Re: [fpc-devel] Sorting tests
On Tue, 29 Nov 2022 15:54:03 +0100 Benito van der Zander via fpc-devel wrote: > Hi, > and the FPC implementation is actually documented to not be stable in >[...] > and one can see that it is indeed not stable, if you sort > ['a','b','A'] case-insensitively, it becomes ['A', 'a','b'] If the current QuickSort is not stable, is there an another argument for keeping it as default? Mattias ___ fpc-devel maillist - fpc-devel@lists.freepascal.org https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
Re: [fpc-devel] Sorting tests
On 11/29/22 22:16, J. Gareth Moreton via fpc-devel wrote: On 29/11/2022 20:03, Nikolay Nikolov via fpc-devel wrote: if (a That's the big one that sorting algorithms rely on... the transitive law. If that is violated, then you cannot guarantee a sorted result. It doesn't matter if (a < b) or (b < a) return False for equal elements, or use (a <=b) or (b <= a) instead, as long as it's consistent. Also have to watch out for more subtle instances of it, like "if (a < b) then DoX else DoY;" and then having "if (b < a) then DoZ else DoQ;". While I do wish people would fix any bugs that are found in their own code, sometimes we do have to accept that this isn't always possible. I think the most famous example I can think of is with SimCity 2000... there was a critical bug in it where memory was used after it was deallocated. Under DOS and Windows 3.1, this wasn't an issue because the memory wouldn't be reused by another application, but under Windows 95 this assumption could no longer hold. So, under the guidance of Raymond Chen, Microsoft programmed Windows 95 to delay actually releasing that block of memory... only for SimCity 2000! Yes. Horrible. :) Another example is Quake 2 or 3 (I forgot which one) having a buffer overflow vulnerability, because of copying (strcpy) the OpenGL extensions string to a C fixed size buffer (char buf[1024] or something like that). After a certain point, OpenGL video cards became so advanced and got so many extensions, that the string, returned by the graphics card simply became too long for that buffer, thus causing Quake to crash instantly on startup. But since nobody wants to buy a video card, that doesn't run Quake, graphics card vendors had to implement a hack - the detect the Quake .exe and report a different, shorter, extensions string. Nikolay 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
Re: [fpc-devel] Sorting tests
On 29/11/2022 20:03, Nikolay Nikolov via fpc-devel wrote: if (a That's the big one that sorting algorithms rely on... the transitive law. If that is violated, then you cannot guarantee a sorted result. It doesn't matter if (a < b) or (b < a) return False for equal elements, or use (a <=b) or (b <= a) instead, as long as it's consistent. Also have to watch out for more subtle instances of it, like "if (a < b) then DoX else DoY;" and then having "if (b < a) then DoZ else DoQ;". While I do wish people would fix any bugs that are found in their own code, sometimes we do have to accept that this isn't always possible. I think the most famous example I can think of is with SimCity 2000... there was a critical bug in it where memory was used after it was deallocated. Under DOS and Windows 3.1, this wasn't an issue because the memory wouldn't be reused by another application, but under Windows 95 this assumption could no longer hold. So, under the guidance of Raymond Chen, Microsoft programmed Windows 95 to delay actually releasing that block of memory... only for SimCity 2000! Kit ___ fpc-devel maillist - fpc-devel@lists.freepascal.org https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
Re: [fpc-devel] Sorting tests
On 11/29/22 16:44, Ondrej Pokorny via fpc-devel wrote: Am 29.11.2022 um 14:25 schrieb Sven Barth via fpc-devel: For such a comparison function the issue is indeed in the comparison function, but Nikolay also mentioned "ais the case for equal elements. I assume this was some kind of typo or reasoning error because "acompare function is correct. And Nikolay was talking about incorrect comparison functions. Yes, I made a mistake, due to being in a hurry, while writing this email. I meant other properties, such as: (a Ondrej ___ 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
Re: [fpc-devel] Sorting tests
How so? Heapsort isn't stable either. Is there a variant I'm not aware of? Kit On 29/11/2022 16:36, Marco van de Voort via fpc-devel wrote: On 29-11-2022 17:34, J. Gareth Moreton via fpc-devel wrote: This is why I hope my own improvement to the version in TArrayHelper could be used instead: https://gitlab.com/freepascal.org/fpc/source/-/merge_requests/334 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=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) Usually it is heapsort that is picked as alternative to quicksort if stable algo is needed. ___ 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
Re: [fpc-devel] Sorting tests
On 29-11-2022 17:34, J. Gareth Moreton via fpc-devel wrote: This is why I hope my own improvement to the version in TArrayHelper could be used instead: https://gitlab.com/freepascal.org/fpc/source/-/merge_requests/334 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=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) Usually it is heapsort that is picked as alternative to quicksort if stable algo is needed. ___ fpc-devel maillist - fpc-devel@lists.freepascal.org https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
Re: [fpc-devel] Sorting tests
This is why I hope my own improvement to the version in TArrayHelper could be used instead: https://gitlab.com/freepascal.org/fpc/source/-/merge_requests/334 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=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) Kit 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 abehavior 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 ___ fpc-devel maillist - fpc-devel@lists.freepascal.org https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
Re: [fpc-devel] Sorting tests
More like a variation of that: TimSort - but that's rather a beast to implement properly and efficient. Am 29.11.2022 um 14:41 schrieb J. Gareth Moreton via fpc-devel: Quicksort is not inherently stable because of what happens if a value is equal to the pivot - more specifically, which of the identical values is selected as the pivot - for example, if you try to sort a list of identical values, they will inevitably change order because each stage will move all of the values to one side of the pivot (and also cause quicksort to degenerate into O(n²)). If you want a stable sort, you need to use things like merge sort instead. Kit On 29/11/2022 13:25, Sven Barth via fpc-devel wrote: Ondrej Pokorny via fpc-devel schrieb am Di., 29. Nov. 2022, 11:39: Am 29.11.2022 um 11:08 schrieb Sven Barth via fpc-devel: J. Gareth Moreton via fpc-devel schrieb am Di., 29. Nov. 2022, 10:09: 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. This *can* be blamed on IntroSort, because Stability (order of equal elements is kept) is an attribute of sorting algorithms and IntroSort is *not* considered stable while QuickSort *can* be stable depending on the implementation and ours *is*. If for two elements [a, b] the comparison function returns aFor such a comparison function the issue is indeed in the comparison function, but Nikolay also mentioned "ais the case for equal elements. Regards, Sven ___ 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
Re: [fpc-devel] Sorting tests
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 abehavior 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
Re: [fpc-devel] Sorting tests
Hi,
and the FPC implementation is actually documented to not be stable in
the code:
{
QuickSort
Average performance: O(n log n)
Worst performance: O(n*n)
Extra memory use: O(log n) on the stack
Stable: no
Additional notes: Uses the middle element asthe pivot. This makes it work
well also on already sorted sequences, which can occur
often in practice. As expected from QuickSort, it works
best on random sequencesand is usually the fastest
algorithm to sort them. It is, however, possible for a
malicious user to craft special sequences, which trigger
its worst O(n*n)case. They can also occur in practice,
although they are veryunlikely. If this is not an
acceptable risk (e.g.for high risk applications,
security-conscious applications or applications with hard
real-time requirements),another sorting algorithm must
be used.
}
and one can see that it is indeed not stable, if you sort ['a','b','A']
case-insensitively, it becomes ['A', 'a','b']
If you want a stable sort, you need to use things like merge sort instead.
I wanted a stable sort and implemented merge sort, and it was far too
slow to be usable.
Now I use the sortbase quicksort, but sort an array of pointers to the
actual array, so the compare function can compare the indices for equal
elements.
Cheers,
Benito
On 29.11.22 14:41, J. Gareth Moreton via fpc-devel wrote:
Quicksort is not inherently stable because of what happens if a value
is equal to the pivot - more specifically, which of the identical
values is selected as the pivot - for example, if you try to sort a
list of identical values, they will inevitably change order because
each stage will move all of the values to one side of the pivot (and
also cause quicksort to degenerate into O(n²)). If you want a stable
sort, you need to use things like merge sort instead.
Kit
On 29/11/2022 13:25, Sven Barth via fpc-devel wrote:
Ondrej Pokorny via fpc-devel schrieb
am Di., 29. Nov. 2022, 11:39:
Am 29.11.2022 um 11:08 schrieb Sven Barth via fpc-devel:
J. Gareth Moreton via fpc-devel
schrieb am Di., 29. Nov. 2022, 10:09:
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.
This *can* be blamed on IntroSort, because Stability (order of
equal elements is kept) is an attribute of sorting algorithms
and IntroSort is *not* considered stable while QuickSort *can*
be stable depending on the implementation and ours *is*.
If for two elements [a, b] the comparison function returns
aFor such a comparison function the issue is indeed in the comparison
function, but Nikolay also mentioned "ais the case for equal elements.
Regards,
Sven
___
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
Re: [fpc-devel] Sorting tests
Where exactly can that stable quicksort be found? rtl/inc/sortbase.pp looks pretty much like standard quicksort to me. Am 29.11.2022 um 11:08 schrieb Sven Barth via fpc-devel: J. Gareth Moreton via fpc-devel schrieb am Di., 29. Nov. 2022, 10:09: 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. This *can* be blamed on IntroSort, because Stability (order of equal elements is kept) is an attribute of sorting algorithms and IntroSort is *not* considered stable while QuickSort *can* be stable depending on the implementation and ours *is*. Regards, Sven ___ 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
Re: [fpc-devel] Sorting tests
Am 29.11.2022 um 14:25 schrieb Sven Barth via fpc-devel: For such a comparison function the issue is indeed in the comparison function, but Nikolay also mentioned "ais the case for equal elements. I assume this was some kind of typo or reasoning error because "acompare function is correct. And Nikolay was talking about incorrect comparison functions. Ondrej ___ fpc-devel maillist - fpc-devel@lists.freepascal.org https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
Re: [fpc-devel] Sorting tests
Quicksort is not inherently stable because of what happens if a value is equal to the pivot - more specifically, which of the identical values is selected as the pivot - for example, if you try to sort a list of identical values, they will inevitably change order because each stage will move all of the values to one side of the pivot (and also cause quicksort to degenerate into O(n²)). If you want a stable sort, you need to use things like merge sort instead. Kit On 29/11/2022 13:25, Sven Barth via fpc-devel wrote: Ondrej Pokorny via fpc-devel schrieb am Di., 29. Nov. 2022, 11:39: Am 29.11.2022 um 11:08 schrieb Sven Barth via fpc-devel: J. Gareth Moreton via fpc-devel schrieb am Di., 29. Nov. 2022, 10:09: 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. This *can* be blamed on IntroSort, because Stability (order of equal elements is kept) is an attribute of sorting algorithms and IntroSort is *not* considered stable while QuickSort *can* be stable depending on the implementation and ours *is*. If for two elements [a, b] the comparison function returns aFor such a comparison function the issue is indeed in the comparison function, but Nikolay also mentioned "ais the case for equal elements. Regards, Sven ___ 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
Re: [fpc-devel] Sorting tests
Ondrej Pokorny via fpc-devel schrieb am Di., 29. Nov. 2022, 11:39: > Am 29.11.2022 um 11:08 schrieb Sven Barth via fpc-devel: > > J. Gareth Moreton via fpc-devel schrieb > am Di., 29. Nov. 2022, 10:09: > >> 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. >> > > This *can* be blamed on IntroSort, because Stability (order of equal > elements is kept) is an attribute of sorting algorithms and IntroSort is > *not* considered stable while QuickSort *can* be stable depending on the > implementation and ours *is*. > > If for two elements [a, b] the comparison function returns > a > then the problem is not in stability or any other feature of the sorting > algorithm but in the comparison function indeed. Or am I missing something? > For such a comparison function the issue is indeed in the comparison function, but Nikolay also mentioned "a ___ fpc-devel maillist - fpc-devel@lists.freepascal.org https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
Re: [fpc-devel] Sorting tests
Am 29.11.2022 um 11:08 schrieb Sven Barth via fpc-devel: J. Gareth Moreton via fpc-devel schrieb am Di., 29. Nov. 2022, 10:09: 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. This *can* be blamed on IntroSort, because Stability (order of equal elements is kept) is an attribute of sorting algorithms and IntroSort is *not* considered stable while QuickSort *can* be stable depending on the implementation and ours *is*. If for two elements [a, b] the comparison function returns athen the problem is not in stability or any other feature of the sorting algorithm but in the comparison function indeed. Or am I missing something? Ondrej ___ fpc-devel maillist - fpc-devel@lists.freepascal.org https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
Re: [fpc-devel] Sorting tests
J. Gareth Moreton via fpc-devel schrieb am Di., 29. Nov. 2022, 10:09: > 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. > This *can* be blamed on IntroSort, because Stability (order of equal elements is kept) is an attribute of sorting algorithms and IntroSort is *not* considered stable while QuickSort *can* be stable depending on the implementation and ours *is*. Regards, Sven > ___ fpc-devel maillist - fpc-devel@lists.freepascal.org https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
Re: [fpc-devel] Sorting tests
Hmmm, that's a problem! Fair enough. Kit On 29/11/2022 09:21, Michael Van Canneyt via fpc-devel wrote: On Tue, 29 Nov 2022, J. Gareth Moreton via fpc-devel wrote: 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. No-one is blaming introsort. It's about not breaking other software that depends on the sort mechanisms provided by the RTL. They were documented as using quicksort. Since we don't control the external functions, we cannot set introsort as the default till we know for sure that all external functions are OK with that. We of course could do that and just tell people to fix their implementation. But that's not very friendly. From their point of view, their function is working fine (it may well be for quicksort which was the default mechanism), and we would break it. Michael. ___ 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
Re: [fpc-devel] Sorting tests
On Tue, 29 Nov 2022, J. Gareth Moreton via fpc-devel wrote: 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. No-one is blaming introsort. It's about not breaking other software that depends on the sort mechanisms provided by the RTL. They were documented as using quicksort. Since we don't control the external functions, we cannot set introsort as the default till we know for sure that all external functions are OK with that. We of course could do that and just tell people to fix their implementation. But that's not very friendly. From their point of view, their function is working fine (it may well be for quicksort which was the default mechanism), and we would break it. Michael.___ fpc-devel maillist - fpc-devel@lists.freepascal.org https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
Re: [fpc-devel] Sorting tests
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 abehavior 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
Re: [fpc-devel] Sorting tests
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 achange, 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
