Sign in to follow this  
vbuser1338

Sorting a list by multiple values

Recommended Posts

vbuser1338    175
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:
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);

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

Share this post


Link to post
Share on other sites
alnite    3436
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:

Original array:
Layer X Y
1 1 6 3
2 1 5 9
3 1 10 3
4 2 8 9
5 2 8 4
6 2 3 4

After sorting by X:
Layer X Y
6 2 3 4
2 1 5 9
1 1 6 3
4 2 8 9
5 2 8 4
3 1 10 3

After sorting by Y:
Layer X Y
1 1 6 3
3 1 10 3
6 2 3 4
5 2 8 4
2 1 5 9
4 2 8 9

After sorting by Layer:
Layer X Y
1 1 6 3
3 1 10 3
2 1 5 9
6 2 3 4
5 2 8 4
4 2 8 9

Share this post


Link to post
Share on other sites
alnite    3436
Quote:
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]

Share this post


Link to post
Share on other sites
iMalc    2466
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:
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);
There are dozens of ways of factoring the same code, including making it all one line with only a single return statement, but I believe what I've written above is one way to solve your problem.

Share this post


Link to post
Share on other sites
hh10k    589
iMalc bead me to it :) My solution was going to be:


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.

Share this post


Link to post
Share on other sites
vbuser1338    175
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.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this