{"id":42063,"date":"2003-10-23T03:18:00","date_gmt":"2003-10-23T03:18:00","guid":{"rendered":"https:\/\/blogs.msdn.microsoft.com\/oldnewthing\/2003\/10\/23\/writing-a-sort-comparison-function\/"},"modified":"2003-10-23T03:18:00","modified_gmt":"2003-10-23T03:18:00","slug":"writing-a-sort-comparison-function","status":"publish","type":"post","link":"https:\/\/devblogs.microsoft.com\/oldnewthing\/20031023-00\/?p=42063","title":{"rendered":"Writing a sort comparison function"},"content":{"rendered":"<p>\nWhen you are writing a sort comparison function (say, to be passed to\n<code>ListView_SortItems<\/code> or *gasp* to be used as\nan <code>IComparer<\/code>), your comparison function needs to follow\nthese rules:\n<\/p>\n<ul>\n<li><b>Reflexivity<\/b>:\n<code>Compare(a, a) = 0<\/code>.<\/p>\n<li><b>Anti-Symmetry<\/b>:\n<code>Compare(a, b)<\/code> has the opposite sign of\n<code>Compare(b, a)<\/code>, where 0 is considered to\nbe its own opposite.<\/p>\n<li><b>Transitivity<\/b>:\nIf <code>Compare(a, b) &le; 0<\/code>\nand <code>Compare(b, c) &le; 0<\/code>,\nthen <code>Compare(a, c) &le; 0<\/code>.\n<\/ul>\n<p>\nHere are some logical consequences of these rules (all easily proved).\nThe first two are obvious, but the third may be a surprise.\n<\/p>\n<ul>\n<li><b>Transitivity of equality<\/b>:\nIf <code>Compare(a, b) = 0<\/code>\nand <code>Compare(b, c) = 0<\/code>,\nthen <code>Compare(a, c) = 0<\/code>.<\/p>\n<li><b>Transitivity of inequality<\/b>:\nIf <code>Compare(a, b) &lt; 0<\/code>\nand <code>Compare(b, c) &lt; 0<\/code>,\nthen <code>Compare(a, c) &lt; 0<\/code>.<\/p>\n<li><b>Substitution<\/b>: If\n<code>Compare(a, b) = 0<\/code>, then\n<code>Compare(a, c)<\/code> has the same sign as\n<code>Compare(b, c)<\/code>.\n<\/ul>\n<p>\nOf the original three rules,\nthe first two are hard to get wrong, but the third rule is\noften hard to get right if you try to be clever in your comparison\nfunction.\n<\/p>\n<p>\nFor one thing, these rules require that you implement a total order.\nIf you merely have a partial order, you must extend your partial\norder to a total order <i>in a consistent manner<\/i>.\n<\/p>\n<p>\nI saw somebody get into trouble when they tried to implement their\ncomparison function on a set of tasks, where some tasks have other\ntasks as prerequisites. The comparison function implemented\nthe following algorithm:\n<\/p>\n<ul>\n<li>If <code>a<\/code> is a prerequisite of <code>b<\/code>\n(possibly through a chain of intermediate tasks),\nthen <code>a &lt; b<\/code>.<\/p>\n<li>If <code>b<\/code> is a prerequisite of <code>a<\/code>\n(again, possibly through a chain of intermediate tasks),\nthen <code>a &gt; b<\/code>.<\/p>\n<li>Otherwise, <code>a = b<\/code>.\n&#8220;Neither task is a prerequisite of the other, so I don&#8217;t care what\norder they are in.&#8221;\n<\/ul>\n<p>\nSounds great. Then you can sort with this comparison function and you\nget the tasks listed in some order such that all tasks come after\ntheir prerequisites.\n<\/p>\n<p>\nExcept that it doesn&#8217;t work. Trying to sort with this comparison\nfunction results in all the tasks being jumbled together\nwith apparently no regard for which tasks are prerequisites of which.\nWhat went wrong?\n<\/p>\n<p>\nConsider this dependency diagram:\n<\/p>\n<pre>\n   a ----&gt; b\n   c\n<\/pre>\n<p>\nTask &#8220;a&#8221; is a prerequisite for &#8220;b&#8221;, and task &#8220;c&#8221; is unrelated to both\nof them. If you used the above comparison function, it would declare\nthat &#8220;a = c&#8221; and &#8220;b = c&#8221; (since &#8220;c&#8221; is unrelated to &#8220;a&#8221; or &#8220;b&#8221;),\nwhich in turn implies by transitivity that &#8220;a = b&#8221;, which contradicts\n&#8220;a &lt; b&#8221;, since &#8220;a&#8221; is a prerequisite for &#8220;b&#8221;.\nIf your comparison function is inconsistent, you will get garbled results.\n<\/p>\n<p>\nMoral of the story: When you write a comparison function, you really\nhave to know which items are less than which other items.\nDon&#8217;t just declare two items &#8220;equal&#8221; because you don&#8217;t know which order\nthey should be in.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>When you are writing a sort comparison function (say, to be passed to ListView_SortItems or *gasp* to be used as an IComparer), your comparison function needs to follow these rules: Reflexivity: Compare(a, a) = 0. Anti-Symmetry: Compare(a, b) has the opposite sign of Compare(b, a), where 0 is considered to be its own opposite. Transitivity: [&hellip;]<\/p>\n","protected":false},"author":1069,"featured_media":111744,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[1],"tags":[25],"class_list":["post-42063","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-oldnewthing","tag-code"],"acf":[],"blog_post_summary":"<p>When you are writing a sort comparison function (say, to be passed to ListView_SortItems or *gasp* to be used as an IComparer), your comparison function needs to follow these rules: Reflexivity: Compare(a, a) = 0. Anti-Symmetry: Compare(a, b) has the opposite sign of Compare(b, a), where 0 is considered to be its own opposite. Transitivity: [&hellip;]<\/p>\n","_links":{"self":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/42063","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/users\/1069"}],"replies":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/comments?post=42063"}],"version-history":[{"count":0,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/42063\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/media\/111744"}],"wp:attachment":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/media?parent=42063"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/categories?post=42063"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/tags?post=42063"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}