\n\nMy program hangs when I used this sort comparison function\n(pseudocode):\n<\/P>\n
\nint compare(x, y)\n{\n return x >y ? +1 : -1;\n}\n<\/PRE>\n\nWhat’s even more strange is that sometimes instead of hanging,\nthe program crashes.\nIt all works correctly if I add one line:\n<\/P>\n
\nint compare2(x, y)\n{\n if (x == y) return 0; \/\/ added<\/FONT>\n return x >y ? +1 : -1;\n}\n<\/PRE>\n\nWhat’s going on?\nThe array I am sorting contains no duplicate elements,\nso the two items x<\/CODE> and y<\/CODE>\nshould never be equal.\n<\/P>\n<\/BLOCKQUOTE>\n\nFirst of all, your first comparison function clearly violates\nthe requirements for being a comparison function:\nIt must return zero if the two items compare equal.\nAs a result, the behavior is undefined, and hanging,\ncrashing, or returning an incorrect result are all legitimate behavior.\n<\/P>\n
\nBut let’s dig a little deeper to see why hanging and crashing\nare plausible responses to an invalid sort comparison function.\n<\/P>\n
\nA common sorting algorithm is quicksort.\nI’ll leave you to go off and learn on your own how the\nquicksort algorithm works.\nCome back when you’re done.\n<\/P>\n
\nOkay, welcome back.\nThe central step in quicksort is the partition,\nand some variants of the quicksort algorithm rely on the\npartition element comparing equal to itself in order to remove\na comparison from the inner loop.\nFor example, an index may walk through the array looking for\nan element greater than or equal to the partition,\nfully expecting at least one such element to be found\nbecause in the worst case, it will find the partition itself.\nBut if your comparison function fails to report the partition\nas equal to itself,\nthis search may run off the end of the array and eventually\ncrash with an access violation when it reaches invalid memory.\n<\/P>\n
\nThat explains the crash, but what about the hang?\nWell,\nnotice that the comparison function is also inconsistent.\nIn particular,\nthe anti-symmetry rule is violated:\ncompare(x, y)<\/CODE> and compare(y, x)<\/CODE>\nreturn the same value (as opposed to the opposite value)\nif x==y<\/CODE>.\nThe function returns -1<\/CODE> both times,\nsaying\n“x<\/CODE> is less than <\/CODE>y<\/CODE>”\nand\n“y<\/CODE> is less than <\/CODE>x<\/CODE>” simultaneously.\nThis inconsistency can easily send a sort algorithm\nrunning back and forth trying to find the right place for\nthe partition.\n<\/P>\n\nThe moral of the story is the same:\nYour comparison function must meet the criteria for\na proper comparison function.\nIf you fail to do this,\nthen the results you get will be very strange indeed.\n<\/P><\/p>\n","protected":false},"excerpt":{"rendered":"
Prerequisites: Experience with sort functions such as qsort. Overqualifications: Familiarity with sort algorithms. If you break the rules for sort comparison functions, then don’t expect the result of a sort call to be meaningful. In fact, if you really mess it up, you can corrupt memory or go into an infinite loop. My program hangs […]<\/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-18313","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-oldnewthing","tag-code"],"acf":[],"blog_post_summary":"
Prerequisites: Experience with sort functions such as qsort. Overqualifications: Familiarity with sort algorithms. If you break the rules for sort comparison functions, then don’t expect the result of a sort call to be meaningful. In fact, if you really mess it up, you can corrupt memory or go into an infinite loop. My program hangs […]<\/p>\n","_links":{"self":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/18313","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=18313"}],"version-history":[{"count":0,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/18313\/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=18313"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/categories?post=18313"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/tags?post=18313"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}