Problem 293. Generalized sorting

Created by S L

Solve Later

{"relationships":[{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/document","targetMode":"","relationshipId":"rId1","target":"/matlab/document.xml"},{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/output","targetMode":"","relationshipId":"rId2","target":"/matlab/output.xml"}],"parts":[{"partUri":"/matlab/document.xml","relationship":[],"contentType":"application/vnd.mathworks.matlab.code.document+xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n<w:document xmlns:w=\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\"><w:body><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Write generalized sort function</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:rFonts w:cs=\"monospace\"/></w:rPr><w:t>sortg()</w:t></w:r><w:r><w:t> that sorts array elements in “ascending” order with given comparison function. A comparison function takes two arguments and return true if the first argument goes before the second in the specific (strick weak) ordering.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>The function have to be stable, that is, if A has elements are “equal” (strictly speaking, both</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:rFonts w:cs=\"monospace\"/></w:rPr><w:t>comp(a1, a2)</w:t></w:r><w:r><w:t> and</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:rFonts w:cs=\"monospace\"/></w:rPr><w:t>comp(a2, a1)</w:t></w:r><w:r><w:t> are false), then the ordering of these elements must be preserved. Since MATLAB's</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:rFonts w:cs=\"monospace\"/></w:rPr><w:t>sort()</w:t></w:r><w:r><w:t> function is stable,</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:rFonts w:cs=\"monospace\"/></w:rPr><w:t>sort(A)</w:t></w:r><w:r><w:t> and</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:rFonts w:cs=\"monospace\"/></w:rPr><w:t>sortg(A, @lt)</w:t></w:r><w:r><w:t> will be equivalent.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>(Assume that the input argument</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:rFonts w:cs=\"monospace\"/></w:rPr><w:t>A</w:t></w:r><w:r><w:t> will be a vector, not a matrix, and the comparison function</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:rFonts w:cs=\"monospace\"/></w:rPr><w:t>comp()</w:t></w:r><w:r><w:t> will do scalar expansion like MATLAB's</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:rFonts w:cs=\"monospace\"/></w:rPr><w:t>lt()</w:t></w:r><w:r><w:t> (</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:rFonts w:cs=\"monospace\"/></w:rPr><w:t>&lt;</w:t></w:r><w:r><w:t> ), that is, comparing scalar with vector is possible.)</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Example</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[ A = [1, 0, 0 + 1i];\n [B, IX] = sortg(A, @(a, b) abs(a) < abs(b));\n\n => B == [0, 1, 0 + 1i];\n IX == [2 1 3]]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>(1 and 0 + 1i have the same absolute value, but 1 has to appear before 0 + 1i, as the original ordering.)</w:t></w:r></w:p></w:body></w:document>"},{"partUri":"/matlab/output.xml","contentType":"text/xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\" ?><embeddedOutputs><metaData><evaluationState>manual</evaluationState><layoutState>code</layoutState><outputStatus>ready</outputStatus></metaData><outputArray type=\"array\"/><regionArray type=\"array\"/></embeddedOutputs>"}]}

Write generalized sort function <tt>sortg()</tt> that sorts array elements in &ldquo;ascending&rdquo; order with given comparison function. A comparison function takes two arguments and return true if the first argument goes before the second in the specific (strick weak) ordering.The function have to be stable, that is, if A has elements are &ldquo;equal&rdquo; (strictly speaking, both <tt>comp(a1, a2)</tt> and <tt>comp(a2, a1)</tt> are false), then the ordering of these elements must be preserved. Since MATLAB's <tt>sort()</tt> function is stable, <tt>sort(A)</tt> and <tt>sortg(A, @lt)</tt> will be equivalent.(Assume that the input argument <tt>A</tt> will be a vector, not a matrix, and the comparison function <tt>comp()</tt> will do scalar expansion like MATLAB's <tt>lt()</tt> ( <tt>&lt;</tt> ), that is, comparing scalar with vector is possible.)Example<pre> A = [1, 0, 0 + 1i];
 [B, IX] = sortg(A, @(a, b) abs(a) &lt; abs(b));</pre><pre> => B == [0, 1, 0 + 1i];
 IX == [2 1 3]</pre>(1 and 0 + 1i have the same absolute value, but 1 has to appear before 0 + 1i, as the original ordering.)

Solve

Solution Stats

65 Solutions
19 Solvers

Last Solution submitted on Sep 25, 2020

Last 200 Solutions

Problem Comments

Solution Comments

Solution 1186148

1 Comment

1 Comment

T. Dunker on 11 May 2017

This solution passes the test cases, yet it fails in general.

Solution 88806

1 Comment

1 Comment

T. Dunker on 11 May 2017

This solution would fail e.g. on a column vector a = randi(10, 100,1)

Problem Recent Solvers19

Problem Tags

sort

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Problem 293. Generalized sorting

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers19

Suggested Problems

More from this Author1

Problem Tags

Community Treasure Hunt

Problem 293. Generalized sorting

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers19

Suggested Problems

More from this Author1

Problem Tags

Community Treasure Hunt

Players