[fpc-devel] Sorting tests
J. Gareth Moreton
gareth at moreton-family.com
Wed Nov 30 00:57:14 CET 2022
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 <fpc-devel at lists.freepascal.org>
> 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 at lists.freepascal.org
> https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
>
More information about the fpc-devel
mailing list