{"id":3441,"date":"2018-05-02T09:19:28","date_gmt":"2018-05-02T08:19:28","guid":{"rendered":"http:\/\/roboblog.fatal-fury.de\/?p=3441"},"modified":"2018-05-02T09:19:28","modified_gmt":"2018-05-02T08:19:28","slug":"c-guns-comment-to-the-sound-of-sorting-audibilization-and-visualization-of-sorting-algorithms","status":"publish","type":"post","link":"http:\/\/roboblog.fatal-fury.de\/?p=3441","title":{"rendered":"C++ Guns: Comment to The Sound of Sorting - \"Audibilization\" and Visualization of Sorting Algorithms"},"content":{"rendered":"<p>Also das Video <a href=\"https:\/\/www.youtube.com\/watch?v=kPRA0W1kECg\">15 Sorting Algorithms in 6 Minutes<\/a> ist ja mal sau genial. Am besten h\u00f6rt sich der Radix Sort an ;) Sehr interessant diese vielen Sortieralgorithmen. Muss man sich unbedingt mal anschaun.<br \/>\nAber der Code f\u00fcr dieses Projekt ist nat\u00fcrlich wieder .... ;)<\/p>\n<p>In dem Video werden die Anzahl der Vergleiche und Array Zugriffe gez\u00e4hlt. Ich frage mich ob so etwas nicht einfacher zu realisieren ist. Da std::sort eine Vergleichsfunktion als Argument annimmt, sollte es sehr einfach sein, die Anzahl der Vergleiche zu z\u00e4hlen. Die anderen beiden Argumente sind Iteratoren. Also m\u00fcsste man den indirection operator \u00fcberladen. Das sollte machbar sein.<\/p>\n<p>Hier mein Versuch. St\u00e4ndig die Iterator Logik bei so Probleme neu zu schreiben ist nicht sch\u00f6n, aber zumindest kann man mit dieser Technik JEDEN Algorithmus untersuchen der Iteratoren akzeptiert. Besser als das gekr\u00fcppel was der andere da macht.<\/p>\n<pre class=\"brush: cpp; title: ; notranslate\" title=\"\">\r\n#include &lt;vector&gt;\r\n#include &lt;algorithm&gt;\r\n#include &lt;iostream&gt;\r\n\r\nstruct CounterIteratorAdapter : public std::vector&lt;int&gt;::iterator {\r\npublic:\r\n    using Base = std::vector&lt;int&gt;::iterator;\r\n\r\n    int&amp; operator*() {\r\n        ++counter;\r\n        return Base::operator *();\r\n    }\r\n\r\n    auto operator+(int rhs) const {\r\n        return CounterIteratorAdapter{Base::operator +(rhs)};\r\n    }\r\n\r\n    auto operator-(int rhs) const {\r\n        return CounterIteratorAdapter{Base::operator -(rhs)};\r\n    }\r\n\r\n    static int counter;\r\n};\r\n\r\nint CounterIteratorAdapter::counter = 0;\r\n\r\nint main() {\r\n    std::vector&lt;int&gt; data(100);\r\n    for(int i=0; i &lt; data.size(); ++i) {\r\n        data&#x5B;i] = data.size()-i;\r\n    }\r\n\r\n    int comparisons = 0;\r\n    auto compare = &#x5B;&amp;comparisons](const int lhs, const int rhs) { ++comparisons; return lhs &lt; rhs;};\r\n\r\n    std::sort(CounterIteratorAdapter{data.begin()}, CounterIteratorAdapter{data.end()}, compare);\r\n\r\n    std::cout &lt;&lt; comparisons &lt;&lt; &quot; comparisons &quot;&lt;&lt; CounterIteratorAdapter::counter &lt;&lt; &quot; array accesses\\n&quot;;\r\n}\r\n<\/pre>\n<blockquote><p>Random:<br \/>\n830 comparisons 2223 array accesses<br \/>\nReserve:<br \/>\n526 comparisons 1355 array accesses<br \/>\nSorted:<br \/>\n629 comparisons 1474 array accesses\n<\/p><\/blockquote>\n","protected":false},"excerpt":{"rendered":"<p>Also das Video 15 Sorting Algorithms in 6 Minutes ist ja mal sau genial. Am besten h\u00f6rt sich der Radix Sort an ;) Sehr interessant diese vielen Sortieralgorithmen. Muss man sich unbedingt mal anschaun. Aber der Code f\u00fcr dieses Projekt ist nat\u00fcrlich wieder .... ;) In dem Video werden die Anzahl der Vergleiche und Array [&hellip;]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4],"tags":[17],"class_list":["post-3441","post","type-post","status-publish","format-standard","hentry","category-allgemein","tag-cpp"],"_links":{"self":[{"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=\/wp\/v2\/posts\/3441","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=3441"}],"version-history":[{"count":5,"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=\/wp\/v2\/posts\/3441\/revisions"}],"predecessor-version":[{"id":3446,"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=\/wp\/v2\/posts\/3441\/revisions\/3446"}],"wp:attachment":[{"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=3441"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=3441"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=3441"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}