[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