I'm writing an algorithm to sort an array of 3D boxes for drawing in front-to-back order. There is a well-defined, stable way to decide which of two boxes is in front of the other, so I have written a function to do that, and then I pass my function to Array.prototype.sort()
to get the correct drawing order.
But it is possible to have cycles of boxes such that A>B
, B>C
and C>A
are all true. This means there is no well-defined sort order for the overall list, even though the order of any pair is well-defined.
In practice, this situation is unlikely to arise, and if it does, I can live with one or two boxes being in the wrong order. But are there JS implementations out there that could sort the whole list wrongly, or crash, under this circumstance?
Just to fill in some more context now the project is done (in fact, no reason you can't look at it if you want):
The reason I asked the question is that, although the obvious answer is "you can't sort using a broken comparator", still... this is a sorting-like task, and attempting to do the sort does give somewhat useful results.
In my specific application, the cyclic case shown above never actually arises (at least, you'd have to be really trying). My hope was that I could sort the objects such that, if you removed any elements that were part of a cycle, the remaining elements would be in strictly correct order. But I didn't get to that point, and here's why:
My first idea was that when I compare two boxes, whichever box is in front on the X axis or the Y axis or the Z axis is sorted in front. But this means that instead of comparing boxes (A), I'm really comparing infinite cross-shapes (B):
--which means they overlap like crazy, and the cyclic situation is not rare at all; in fact it's so common that, with 3 or more objects, I might as well use a random order.
At some point I saw this helpful reference, which suggested that I should only test pairs of boxes that actually overlap on screen. Adding that test (and sorting boxes as "equal" if they don't overlap) gave better results, with boxes in the right order more often than not, but still with lots of errors.
The problem is that fast sorting algorithms don't test every possible pair of values (they'd be O(n2) if they did). Sorting A and B as "equal" doesn't simply mean that their relative order is unimportant; it means that if C sorts before A, it must also sort before B. No matter what sort algorithm a browser uses, it will skip comparisons based on this assumption, and therefore it will not test every pair of boxes that I need it to test.
In the end, I wrote my own inefficent, naïve sorting code (test every box until I find an overlap). I never have more than 40 objects on screen, so the performance is OK, and the result is correct often enough. A more thorough algorithm would involve backtracking, and would raise halting issues, so I stopped here.
So, not the most satisfying conclusion, but sometimes that's how it goes. Hopefully this will provide some help (or cruel amusement) to someone else, anyway.
The purpose of the compare function is to define an alternative sort order. When the sort() function compares two values, it sends the values to the compare function, and sorts the values according to the returned (negative, zero, positive) value. If the result is negative, a is sorted before b .
All of the arguments must be the same size. If the sort order argument is not -1, or 1, the formula will result in a #VALUE! error. If you leave out the sort order argument, Excel will default to ascending order.
The primary difference between the two is that list. sort() will sort the list in-place, mutating its indexes and returning None , whereas sorted() will return a new sorted list leaving the original list unchanged.
The sort() method sorts the elements of an array in place and returns the reference to the same array, now sorted. The default sort order is ascending, built upon converting the elements into strings, then comparing their sequences of UTF-16 code units values.
If the ordering is not transitive – as you say, the type allows for circular relationships A > B ; B > C ; C > A
– then I don't know what it would mean for the items to be in the wrong order :-)
The standard for ECMAScript (ECMA-262, 5.1 Edition) says of Array.prototype.sort
:
If
comparefn
is not undefined and is not a consistent comparison function for the elements of this array (see below), the behaviour ofsort
is implementation-defined.
and the “see below” explains that, yes, transitivity of comparisons is needed for a comparefn to qualify as “consistent”.
A function
comparefn
is a consistent comparison function for a set of valuesS
if all of the requirements below are met […]
- If
a =CF b
andb =CF c
, thena =CF c
(transitivity of=CF
)- If
a < CF b
andb <\ CF c
, thena <\ CF c
(transitivity of<\ CF
)- If
a >CF b
andb >CF c
, thena >CF c
(transitivity of>CF
)
So, as you describe it, your non-transitive comparison function invokes the “implementation-defined” clause of the specification.
And I would recommend reading “implementation-defined” as “can do anything or nothing, unpredictably, and still be compliant with this specification”.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With