Sort stability: Difference between revisions
Content added Content deleted
Line 768: | Line 768: | ||
.say for @cities.sort: { .[1] };</lang> |
.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}}== |
=={{header|PHP}}== |