## Writing a sort comparison function

 Date: October 23, 2003 / year-entry #106 Tags: code Orig Link: https://blogs.msdn.microsoft.com/oldnewthing/20031023-00/?p=42063 Comments: 8 Summary: 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:...

 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: If `Compare(a, b) ≤ 0` and `Compare(b, c) ≤ 0`, then `Compare(a, c) ≤ 0`. Here are some logical consequences of these rules (all easily proved). The first two are obvious, but the third may be a surprise. Transitivity of equality: If `Compare(a, b) = 0` and `Compare(b, c) = 0`, then `Compare(a, c) = 0`. Transitivity of inequality: If `Compare(a, b) < 0` and `Compare(b, c) < 0`, then `Compare(a, c) < 0`. Substitution: If `Compare(a, b) = 0`, then `Compare(a, c)` has the same sign as `Compare(b, c)`. Of the original three rules, the first two are hard to get wrong, but the third rule is often hard to get right if you try to be clever in your comparison function. For one thing, these rules require that you implement a total order. If you merely have a partial order, you must extend your partial order to a total order in a consistent manner. I saw somebody get into trouble when they tried to implement their comparison function on a set of tasks, where some tasks have other tasks as prerequisites. The comparison function implemented the following algorithm: If `a` is a prerequisite of `b` (possibly through a chain of intermediate tasks), then `a < b`. If `b` is a prerequisite of `a` (again, possibly through a chain of intermediate tasks), then `a > b`. Otherwise, `a = b`. "Neither task is a prerequisite of the other, so I don't care what order they are in." Sounds great. Then you can sort with this comparison function and you get the tasks listed in some order such that all tasks come after their prerequisites. Except that it doesn't work. Trying to sort with this comparison function results in all the tasks being jumbled together with apparently no regard for which tasks are prerequisites of which. What went wrong? Consider this dependency diagram: ``` a ----> b c ``` Task "a" is a prerequisite for "b", and task "c" is unrelated to both of them. If you used the above comparison function, it would declare that "a = c" and "b = c" (since "c" is unrelated to "a" or "b"), which in turn implies by transitivity that "a = b", which contradicts "a < b", since "a" is a prerequisite for "b". If your comparison function is inconsistent, you will get garbled results. Moral of the story: When you write a comparison function, you really have to know which items are less than which other items. Don't just declare two items "equal" because you don't know which order they should be in.

 Comments (8) Andy says: Sorry if this is slightly off-topic, but what is wrong with IComparer? Israel says: I would guess that it’s because a .Net interface (or a .Net anything) is normally not seen on this blog. See the tagline at top right! :-) Jonathan says: The solution to the IComparer for Tasks is too compare another task field after the dependency comparison showed nothing. For instance: int compare(Task a, Task b) { if (a.dependsOn(b)) return 1; if (b.dependsOn(a)) return -1; return strcmp(a.getName(), b.getName()); // or return a.getId() – b.getId(); if you don’t like the sort order depending on the task name which could change. } Raymond Chen says: Sorry, Jonathan, that still doesn’t work. Consider this dependency diagram: c -> a b then a a b there is no dependency betwen b and anything. With that I’m closing comments since this thread is extremely old. The Old New Thing says: Files and directories with no time/date are often mistaken for so-called Comments are closed.

*DISCLAIMER: I DO NOT OWN THIS CONTENT. If you are the owner and would like it removed, please contact me. The content herein is an archived reproduction of entries from Raymond Chen's "Old New Thing" Blog (most recent link is here). It may have slight formatting modifications for consistency and to improve readability.

WHY DID I DUPLICATE THIS CONTENT HERE? Let me first say this site has never had anything to sell and has never shown ads of any kind. I have nothing monetarily to gain by duplicating content here. Because I had made my own local copy of this content throughout the years, for ease of using tools like grep, I decided to put it online after I discovered some of the original content previously and publicly available, had disappeared approximately early to mid 2019. At the same time, I present the content in an easily accessible theme-agnostic way.

The information provided by Raymond's blog is, for all practical purposes, more authoritative on Windows Development than Microsoft's own MSDN documentation and should be considered supplemental reading to that documentation. The wealth of missing details provided by this blog that Microsoft could not or did not document about Windows over the years is vital enough, many would agree an online "backup" of these details is a necessary endeavor. Specifics include:
• A "redesign" after 2019 erased thousands of user's comments from previous years. As many have stated, the comments are nearly as important as the postings themselves. The archived copies of the postings contained here retain the original comments.
• The blog has changed domains many times and the urls have otherwise been under constant change since 2003. Even when proper redirection has been set up for those links, redirection only works for a limited period of time. For example, all of the internal blog links that were valid in early 2019, were broken by 2020 without proper redirection.
• The blog has been under constant re-design and re-theming since its inception. It is downright irritating to deal with a bogged-down site experience as the result of the latest visual themes designed for cell-phone browsers. As of this writing, it is cumbersome to navigate titles with only 10 entries per page. While it is nice that the official site has a search feature, searching using this index (with all titles on a single page) is much quicker (CTRL-F in most browsers).

<-- Back to Old New Thing Archive Index