<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
</head>
<body>
<p>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.</p>
<p>Kit</p>
<div class="moz-cite-prefix">On 29/11/2022 13:25, Sven Barth via
fpc-devel wrote:<br>
</div>
<blockquote type="cite"
cite="mid:CAFMUeB9f5-cFxQTXxffvNAPb1XJW9EzmG+wN=zGjxHnZ1tA7Ww@mail.gmail.com">
<meta http-equiv="content-type" content="text/html; charset=UTF-8">
<div dir="auto">
<div>
<div class="gmail_quote">
<div dir="ltr" class="gmail_attr">Ondrej Pokorny via
fpc-devel <<a
href="mailto:fpc-devel@lists.freepascal.org"
moz-do-not-send="true" class="moz-txt-link-freetext">fpc-devel@lists.freepascal.org</a>>
schrieb am Di., 29. Nov. 2022, 11:39:<br>
</div>
<blockquote class="gmail_quote" style="margin:0 0 0
.8ex;border-left:1px #ccc solid;padding-left:1ex">
<div>
<div>Am 29.11.2022 um 11:08 schrieb Sven Barth via
fpc-devel:<br>
</div>
<blockquote type="cite">
<div dir="auto">
<div>
<div class="gmail_quote">
<div dir="ltr" class="gmail_attr">J. Gareth
Moreton via fpc-devel <<a
href="mailto:fpc-devel@lists.freepascal.org"
target="_blank" rel="noreferrer"
moz-do-not-send="true"
class="moz-txt-link-freetext">fpc-devel@lists.freepascal.org</a>>
schrieb am Di., 29. Nov. 2022, 10:09:<br>
</div>
<blockquote class="gmail_quote" style="margin:0
0 0 .8ex;border-left:1px #ccc
solid;padding-left:1ex">Surely that's a bug in
the comparison functions that should be fixed
and <br>
not something that can be blamed on
introsort. If a comparison function <br>
is faulty, then pretty nuch any sorting
algorithm can be considered to <br>
have unpredictable behaviour.<br>
</blockquote>
</div>
</div>
<div dir="auto"><br>
</div>
<div dir="auto">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*.</div>
</div>
</blockquote>
<p>If for two elements [a, b] the comparison function
returns<br>
a<b=true and b<a=true</p>
<p>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?</p>
</div>
</blockquote>
</div>
</div>
<div dir="auto"><br>
</div>
<div dir="auto">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. </div>
<div dir="auto"><br>
</div>
<div dir="auto">Regards, </div>
<div dir="auto">Sven </div>
<div dir="auto">
<div class="gmail_quote">
<blockquote class="gmail_quote" style="margin:0 0 0
.8ex;border-left:1px #ccc solid;padding-left:1ex">
</blockquote>
</div>
</div>
</div>
<br>
<fieldset class="moz-mime-attachment-header"></fieldset>
<pre class="moz-quote-pre" wrap="">_______________________________________________
fpc-devel maillist - <a class="moz-txt-link-abbreviated" href="mailto:fpc-devel@lists.freepascal.org">fpc-devel@lists.freepascal.org</a>
<a class="moz-txt-link-freetext" href="https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel">https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel</a>
</pre>
</blockquote>
</body>
</html>