[fpc-devel] Sorting tests

[Benito van der Zander]

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 <fpc-devel at lists.freepascal.org> 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 <fpc-devel at lists.freepascal.org>
>>>     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<b=true and b<a=true
>>
>>     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<b=false and b<a=false" which 
>> is the case for equal elements.
>>
>> Regards,
>> Sven
>>
>>
>> _______________________________________________
>> fpc-devel maillist  -fpc-devel at lists.freepascal.org
>> https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
>
> _______________________________________________
> fpc-devel maillist  -fpc-devel at lists.freepascal.org
> https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.freepascal.org/pipermail/fpc-devel/attachments/20221129/8e67bf8f/attachment-0001.htm>