Sort stability: Difference between revisions

Sort stability (view source)

Revision as of 01:20, 8 April 2022

5,468 bytes added , 2 years ago

m

→‎{{header|Phix}}: syntax coloured, simplified a bit, and actually sort on the second column as per task description

Petelomax

7,804

edits

Revision as of 19:10, 8 December 2021 (view source) Jjuanhdez (talk \| contribs) (Sort stability en FreeBASIC) ← Older edit		Revision as of 01:20, 8 April 2022 (view source) Petelomax (talk \| contribs) m (→‎{{header\|Phix}}: syntax coloured, simplified a bit, and actually sort on the second column as per task description) Newer edit →
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 that a simple tag sort is irrefutably stable since it explicitly orders by tag (aka original position) within any equal keys. <!--<lang Phix>(phixonline)--> ~~that a simple tag sort is guaranteed stable by dint of ordering by tag should the keys be equal.~~ <span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> ~~<lang Phix>sequence test = {{"UK","London"},~~ <span style="color: #004080;">sequence</span> <span style="color: #000000;">test</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{{</span><span style="color: #008000;">"UK"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"London"</span><span style="color: #0000FF;">},</span> ~~{"US","New York"},~~ <span style="color: #0000FF;">{</span><span style="color: #008000;">"US"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"New York"</span><span style="color: #0000FF;">},</span> {"US","Birmingham"},▼ <span style="color: #0000FF;">{</span><span style="color: #008000;">"US"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Birmingham"</span><span style="color: #0000FF;">},</span> ~~{"UK","Birmingham"}}~~ <span style="color: #0000FF;">{</span><span style="color: #008000;">"UK"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Birmingham"</span><span style="color: #0000FF;">}}</span> ---------------------▼ <span style="color: #000080;font-style:italic;">--------------------- -- probably stable -- ---------------------▼ ▲ ---------------------</span> ~~function cmp(object a, object b)~~ <span style="color: #008080;">function</span> <span style="color: #000000;">cmp</span><span style="color: #0000FF;">(</span><span style="color: #004080;">object</span> <span style="color: #000000;">a</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">object</span> <span style="color: #000000;">b</span><span style="color: #0000FF;">)</span> ~~return compare(a[1],b[1])~~ <span style="color: #008080;">return</span> <span style="color: #7060A8;">compare</span><span style="color: #0000FF;">(</span><span style="color: #000000;">a</span><span style="color: #0000FF;">[</span><span style="color: #000000;">2</span><span style="color: #0000FF;">],</span><span style="color: #000000;">b</span><span style="color: #0000FF;">[</span><span style="color: #000000;">2</span><span style="color: #0000FF;">])</span> ~~end function~~ <span style="color: #008080;">end</span> <span style="color: #008080;">function</span> ~~test = custom_sort(routine_id("cmp"),test)~~ <span style="color: #000000;">test</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">custom_sort</span><span style="color: #0000FF;">(</span><span style="color: #000000;">cmp</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">test</span><span style="color: #0000FF;">))</span> ~~pp(test,{pp_Nest,1})~~ <span style="color: #7060A8;">pp</span><span style="color: #0000FF;">(</span><span style="color: #000000;">test</span><span style="color: #0000FF;">,{</span><span style="color: #004600;">pp_Nest</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">})</span> ~~-----------------------~~ <span style="color: #000080;font-style:italic;">----------------------- -- guaranteed stable -- ~~-----------------------~~ ▲ -----------------------</span> ~~function tag_cmp(integer i, integer j)~~ <span style="color: #008080;">function</span> <span style="color: #000000;">tag_cmp</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">)</span> ~~return compare({test[i][1],i},{test[j][1],j})~~ <span style="color: #004080;">integer</span> <span style="color: #000000;">c</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">compare</span><span style="color: #0000FF;">(</span><span style="color: #000000;">test</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">2</span><span style="color: #0000FF;">],</span><span style="color: #000000;">test</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">][</span><span style="color: #000000;">2</span><span style="color: #0000FF;">])</span> ~~-- return compare(test[i][1],test[j][1])~~ <span style="color: #008080;">if</span> <span style="color: #000000;">c</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #000000;">c</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">compare</span><span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">,</span><span style="color: #000000;">j</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> <span style="color: #000080;font-style:italic;">-- (see note)</span> ~~end function~~ <span style="color: #008080;">return</span> <span style="color: #000000;">c</span> ~~sequence tags = custom_sort(routine_id("tag_cmp"),shuffle(tagset(4)))~~ <span style="color: #008080;">end</span> <span style="color: #008080;">function</span> ~~for i=1 to length(tags) do~~ <span style="color: #004080;">sequence</span> <span style="color: #000000;">tags</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">custom_sort</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tag_cmp</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">shuffle</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">tagset</span><span style="color: #0000FF;">(</span><span style="color: #000000;">4</span><span style="color: #0000FF;">)))</span> ~~?test[tags[i]]~~ <span style="color: #7060A8;">pp</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">extract</span><span style="color: #0000FF;">(</span><span style="color: #000000;">test</span><span style="color: #0000FF;">,</span><span style="color: #000000;">tags</span><span style="color: #0000FF;">),{</span><span style="color: #004600;">pp_Nest</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">})</span> ~~end for~~<!--</lang>--> {{Out}} <pre> {{~~"UK"~~`US`, ~~"London"~~`Birmingham`}, {"`UK"`, "`Birmingham"`}, {~~"US"~~`UK`, ~~"New York"~~`London`}, {"`US"`, ~~"Birmingham"~~`New York`}} ▲ {"{`US"`," `Birmingham"`}, {"UK","London"}▼ {"`UK"`," `Birmingham"`}, ▲ {"`UK"`," `London"`}, ~~{"US","New York"}~~ {"`US"`,~~"Birmingham"~~ `New York`}} </pre> ~~The~~Commenting ~~commented-~~out ~~line~~the c=0 fixup in tag_cmp ismakes 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}}==