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.)

Write generalized sort function |sortg()| 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.

(Assume that the input argument |A| will be a vector, not a matrix, and the comparison function |comp()| will do scalar expansion like MATLAB's |lt()| ( |<| ), that is, comparing scalar with vector is possible.)

*Example*

A = [1, 0, 0 + 1i];
 [B, IX] = sortg(A, @(a, b) abs(a) < abs(b));

=> B == [0, 1, 0 + 1i];
       IX == [2 1 3]

(1 and 0 + 1i have the same absolute value, but 1 has to appear before 0 + 1i, as the original ordering.)

Solve

Solution Stats

70 Solutions
19 Solvers

Last Solution submitted on Aug 04, 2021

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!