Sort stability: Difference between revisions

Line 1,347:

=={{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

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 irrefutably stable since it explicitly orders by tag (aka original position) within any equal keys.

that a simple tag sort is guaranteed stable by dint of ordering by tag should the keys be equal.

with javascript_semantics

<lang Phix>sequence test = {{"UK","London"},

sequence test = {{"UK","London"},

{"US","New York"},

{"US","New York"},

⚫

{"US","Birmingham"},

{"US","Birmingham"},

{"UK","Birmingham"}}

{"UK","Birmingham"}}

⚫

---------------------

---------------------

-- probably stable --

⚫

---------------------

⚫

---------------------

function cmp(object a, object b)

function cmp(object a, object b)

return compare(a[1],b[1])

return compare(a[2],b[2])

end function

end function

test = custom_sort(routine_id("cmp"),test)

test = custom_sort(cmp,deep_copy(test))

pp(test,{pp_Nest,1})

pp(test,{pp_Nest,1})

-----------------------

-----------------------

-- guaranteed stable --

-----------------------

⚫

-----------------------

function tag_cmp(integer i, integer j)

function tag_cmp(integer i, integer j)

return compare({test[i][1],i},{test[j][1],j})

integer c = compare(test[i][2],test[j][2])

-- return compare(test[i][1],test[j][1])

if c=0 then c = compare(i,j) end if -- (see note)

end function

return c

sequence tags = custom_sort(routine_id("tag_cmp"),shuffle(tagset(4)))

end function

for i=1 to length(tags) do

sequence tags = custom_sort(tag_cmp,shuffle(tagset(4)))

?test[tags[i]]

pp(extract(test,tags),{pp_Nest,1})

~~end for~~</lang>

<pre>

{{~~"UK"~~, ~~"London"~~},

{{`US`, `Birmingham`},

{"UK", "Birmingham"},

{`UK`, `Birmingham`},

{~~"US"~~, ~~"New York"~~},

{`UK`, `London`},

{"US", ~~"Birmingham"~~}}

{`US`, `New York`}}

⚫

{{`US`, `Birmingham`},

⚫

{"UK","London"}

{"UK","Birmingham"}

{`UK`, `Birmingham`},

⚫

{`UK`, `London`},

{"US","New York"}

{"US",~~"Birmingham"~~}

{`US`, `New York`}}

</pre>

~~The~~ ~~commented-~~out ~~line~~ in tag_cmp is unstable, or rather probably stable wrt the shuffle, whereas the active line guarantees

Commenting out the c=0 fixup in tag_cmp makes it unstable, or rather probably stable wrt the shuffle, and sometimes shows the first two lines flipped, 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 stable"'' (part 2) only guarantees not to upset what the ''"probably stable"'' (part 1) left behind, in other words be sure to delete the first sort ''before'' doing any further testing on the second sort, 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.

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}}==