<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
</head>
<body smarttemplateinserted="true">
<div id="smartTemplate4-template">Hi,<br>
and the FPC implementation is actually documented to not be stable
in the code:</div>
<div>
<pre class="code highlight" lang="delphi"><span id="LC44" data-testid="content" class="line" lang="delphi"><span class="hljs-comment"><span class="hljs-comment"></span></span></span><span id="LC43" data-testid="content" class="line" lang="delphi"></span>
<span id="LC44" data-testid="content" class="line" lang="delphi"><span class=""></span><span class="hljs-comment"><span class="hljs-comment">{</span></span></span>
<span id="LC45" data-testid="content" class="line" lang="delphi"><span class="hljs-comment"> QuickSort</span></span>
<span id="LC46" data-testid="content" class="line" lang="delphi"><span class="hljs-comment"></span></span>
<span id="LC47" data-testid="content" class="line" lang="delphi"><span class="hljs-comment"> Average performance: O(n log n)</span></span>
<span id="LC48" data-testid="content" class="line" lang="delphi"><span class="hljs-comment"> Worst performance: O(n*n)</span></span>
<span id="LC49" data-testid="content" class="line" lang="delphi"><span class="hljs-comment"></span><span class="hljs-comment"> Extra memory use: </span><span class="hljs-comment">O(log n) on the stack</span></span>
<span id="LC50" data-testid="content" class="line" lang="delphi"><span class="hljs-comment"> Stable: no</span></span>
<span id="LC51" data-testid="content" class="line" lang="delphi"><span class="hljs-comment"></span><span class="hljs-comment"> Additional notes: Uses </span><span class="hljs-comment">the middle element as</span><span class="hljs-comment"> the pivot. This </span><span class="hljs-comment">makes it work</span></span>
<span id="LC52" data-testid="content" class="line" lang="delphi"><span class="hljs-comment"></span><span class="hljs-comment"> well also on </span><span class="hljs-comment">already sorted sequences, which can occur</span></span>
<span id="LC53" data-testid="content" class="line" lang="delphi"><span class="hljs-comment"></span><span class="hljs-comment"> often in practice. </span><span class="hljs-comment">As expected from QuickSort, it works</span></span>
<span id="LC54" data-testid="content" class="line" lang="delphi"><span class="hljs-comment"></span><span class="hljs-comment"> best on random </span><span class="hljs-comment">sequences</span><span class="hljs-comment"> and is usually </span><span class="hljs-comment">the fastest</span></span>
<span id="LC55" data-testid="content" class="line" lang="delphi"><span class="hljs-comment"></span><span class="hljs-comment"> algorithm to sort </span><span class="hljs-comment">them. It is, however, possible for a</span></span>
<span id="LC56" data-testid="content" class="line" lang="delphi"><span class="hljs-comment"></span><span class="hljs-comment"> malicious user to </span><span class="hljs-comment">craft special sequences, which trigger</span></span>
<span id="LC57" data-testid="content" class="line" lang="delphi"><span class="hljs-comment"> its worst O(n*n)</span><span class="hljs-comment"> case. They can </span><span class="hljs-comment">also occur in practice,</span></span>
<span id="LC58" data-testid="content" class="line" lang="delphi"><span class="hljs-comment"></span><span class="hljs-comment"> although they are </span><span class="hljs-comment">very</span><span class="hljs-comment"> unlikely. If this </span><span class="hljs-comment">is not an</span></span>
<span id="LC59" data-testid="content" class="line" lang="delphi"><span class="hljs-comment"> acceptable risk (e.g.</span><span class="hljs-comment"> for high risk </span><span class="hljs-comment">applications,</span></span>
<span id="LC60" data-testid="content" class="line" lang="delphi"><span class="hljs-comment"> security-conscious applications or applications with hard</span></span>
<span id="LC61" data-testid="content" class="line" lang="delphi"><span class="hljs-comment"> real-time requirements),</span><span class="hljs-comment"> another sorting algorithm </span><span class="hljs-comment">must</span></span>
<span id="LC62" data-testid="content" class="line" lang="delphi"><span class="hljs-comment"> be used.</span></span>
<span id="LC63" data-testid="content" class="line" lang="delphi"><span class="hljs-comment">}</span></span>
</pre>
<p>and one can see that it is indeed not stable, if you sort
['a','b','A'] case-insensitively, it becomes ['A', 'a','b']<br>
</p>
<br>
</div>
<div>
<blockquote type="cite">If you want a stable sort, you need to use
things like merge sort instead.</blockquote>
</div>
<div><br>
</div>
<div>I wanted a stable sort and implemented merge sort, and it was
far too slow to be usable.</div>
<div><br>
</div>
<div>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. <br>
</div>
<div><br>
</div>
<div><br>
Cheers,<br>
Benito </div>
<div class="moz-cite-prefix">On 29.11.22 14:41, J. Gareth Moreton
via fpc-devel wrote:<br>
</div>
<blockquote type="cite"
cite="mid:4869ed42-afc4-321a-e2ed-efbe051b0f45@moreton-family.com">
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<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 moz-txt-link-freetext" href="mailto:fpc-devel@lists.freepascal.org" moz-do-not-send="true">fpc-devel@lists.freepascal.org</a>
<a class="moz-txt-link-freetext" href="https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel" moz-do-not-send="true">https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel</a>
</pre>
</blockquote>
<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>