Weird Behavior of std::sort (and std::stable_sort), or it's my fault?

Revision en1, by xuanquang1999, 2015-11-22 15:50:25

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:

Code used Bubble sort

But std::sort gave wrong sorting order (more specific, box 5 should stay before box 1):

Code used std::sort

std::stable_sort also gave wrong sorting order:

Code used std::stable_sort

Did something go wrong with my implementation? Or something went wrong with std::sort and std::stable_sort?

Tags sorting, stl


  Rev. Lang. By When Δ Comment
en1 English xuanquang1999 2015-11-22 15:50:25 916 Initial revision (published)