bool SortLayers(const CLayeredTile &t1,const CLayeredTile &t2) {
// Sort by layer, then y, then x
if(t1.layer < t2.layer)
return true;
else if(t1.y < t2.y)
return true;
else if(t1.x < t2.x)
return true;
return false;
}
std::sort(layeredTiles.begin(),layeredTiles.end(),SortLayers);
Sorting a list by multiple values
Author
I have done some searching and trying different code but I haven't found a way to sort a list by multiple values. I want it to sort by layer, then y coordinate and then x coordinate so that I can render an isometric map correctly for the layered portions. The best way I have gotten so far was this:
But this does not work exactly like I want. It will sort correctly but sometimes I have to sort twice to get them sorted correctly when the tiles are all on one layer, but when I have tiles on multiple layers the sorting barely works at all. The only way I can see to get it working is to sort by layer then find where each differnt layer begins and sort from there to the end of the layer for y values, and then sort each one of the y groups for x value then. This does not seem like the best way to sort my list, does anyone know a better way I could use.
Thanks,
vbuser
You are sorting by three different values, the best solution I could think of off the top of my head is to sort your list three times, first by x, second by y, and third by layer (note that the order is backward), and your sorting algorithm must be stable [1].
consider this example:
consider this example:
Original array: Layer X Y1 1 6 32 1 5 93 1 10 34 2 8 95 2 8 46 2 3 4After sorting by X: Layer X Y6 2 3 42 1 5 91 1 6 34 2 8 95 2 8 43 1 10 3After sorting by Y: Layer X Y1 1 6 33 1 10 36 2 3 45 2 8 42 1 5 94 2 8 9After sorting by Layer: Layer X Y1 1 6 33 1 10 32 1 5 96 2 3 45 2 8 44 2 8 9Quote:Original post by Boder
Is that basically a radix sort? Or is a radix sort only called that for strings?
No. It can be any sorting algorithm, but it must be stable. This is important to maintain the previous ordering.
[Edited by - alnite on March 27, 2006 2:36:48 AM]
Your comparisoin function is incorrect. Think about what happens when t1.layer > t2.layer, or when t1.y > t2.y
what you need to write is more like the following:
what you need to write is more like the following:
bool SortLayers(const CLayeredTile &t1,const CLayeredTile &t2) { // Sort by layer, then y, then x if(t1.layer < t2.layer) return true; else if(t1.layer == t2.layer) { if(t1.y < t2.y) return true; else if(t1.y == t2.y) { if(t1.x < t2.x) return true; } } return false;} std::sort(layeredTiles.begin(),layeredTiles.end(),SortLayers);
iMalc bead me to it :) My solution was going to be:
Edit: If you're interested in radix sort, I would recommend the one here, since he describes how to deal with floating point values.
bool IsLayerLess(const CLayeredTile &t1,const CLayeredTile &t2) { // Sort by layer, then y, then x if (t1.layer != t2.layer) return (t1.layer < t2.layer); if (t1.y != t2.y) return (t1.y < t2.y); return (t1.x < t2.x);} std::sort(layeredTiles.begin(), layeredTiles.end(), IsLayerLess);Edit: If you're interested in radix sort, I would recommend the one here, since he describes how to deal with floating point values.
Author
I wasn't thinking about what happens when the layer or y component are greater when I was looking at some text output wondering why it was not sorting correctly. Thanks for the help, now its time to go code some more and hopefully don't run into any more problems:P.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement