Sort stability: Difference between revisions
→{{header|Phix}}
Line 768:
.say for @cities.sort: { .[1] };</lang>
=={{header|Phix}}==
The standard sort method is merge sort, which is apparently stable, though I would be reluctant to guarantee that, or rely on it, especially given
that a simple tag sort is guaranteed stable by dint of ordering by tag should the keys be equal.
<lang Phix>sequence test = {{"UK","London"},
{"US","New York"},
{"US","Birmingham"},
{"UK","Birmingham"}}
---------------------
-- probably stable --
---------------------
function cmp(object a, object b)
return compare(a[1],b[1])
end function
test = custom_sort(routine_id("cmp"),test)
pp(test,{pp_Nest,1})
-----------------------
-- guaranteed stable --
-----------------------
function tag_cmp(integer i, integer j)
return compare({test[i][1],i},{test[j][1],j})
-- return compare(test[i][1],test[j][1])
end function
sequence tags = custom_sort(routine_id("tag_cmp"),shuffle(tagset(4)))
for i=1 to length(tags) do
?test[tags[i]]
end for</lang>
{{Out}}
<pre>
{{"UK", "London"},
{"UK", "Birmingham"},
{"US", "New York"},
{"US", "Birmingham"}}
{"UK","London"}
{"UK","Birmingham"}
{"US","New York"}
{"US","Birmingham"}
</pre>
The commented-out line in tag_cmp is unstable, or rather probably stable wrt the shuffle, whereas the active line guarantees
original (pre-shuffle) ordering, even if an unstable underlying sort method were used.
Obviously, written the way it is above, the guaranteed part only guarantees not to upset what the probably part left behind, and of course test=sort(test) guarantees alphabetical on second column within matching first column. Lastly, preserving a primary tag sort ordering within a secondary tag sort is a bit more mind-bending, but even that is not particularly difficult.
=={{header|PHP}}==
| |||