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 <fpc-devel@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@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@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
