I'm trying to solve 103 — Stacking Boxes on UVa online judge. My idea is first, sort all the box that no box can be nested in the previous box, then run O(n^2) LIS DP on it.
However, when I print the order and the sizes of all boxes, I found something weird:
The Bubble sort algorithm gave correct sorting order:
But std::sort gave wrong sorting order (more specific, box 5 should stay before box 1):
std::stable_sort also gave wrong sorting order:
Did something go wrong with my implementation? Or something went wrong with std::sort and std::stable_sort?
There are two requirements for comparator if you want general sorting algorithms to work:
1) comparator should be transitive.
2) Let's call elements a and b uncomparable if both a < b and b < a are false. Then uncomparability should be equivalence relation (transitive, reflexive and symmetric).
Clearly, your comparator does not satisfy second quality (uncomparability is not transitive). Bubble sort uses only local comparisons, so it may work in this case (because there exist permutation that "is sorted" according to this comparator), but faster algorithms that use bigger knowledge about comparator to fasten up (if comparator only satisfies quality 1, then only topological sorting is guaranteed to work for any comparator satisfying this quality, which is too slow) may produce incorrect result.
I got it. Thanks!