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

64 Solutions
18 Solvers

Last Solution submitted on Oct 29, 2018

Last 200 Solutions

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 Solvers18

Problem Tags

sort

Problem 293. Generalized sorting

Solution Stats

Last 200 Solutions

Solution Comments

Problem Recent Solvers18

Suggested Problems

More from this Author1

Problem Tags

Problem 293. Generalized sorting

Solution Stats

Last 200 Solutions

Solution Comments

Problem Recent Solvers18

Suggested Problems

More from this Author1

Problem Tags

Players