# Sorting a list by multiple values

This topic is 4499 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

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 on other sites
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     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     9

##### Share on other sites
Is that basically a radix sort? Or is a radix sort only called that for strings?

##### Share on other sites
Note that std::sort is not neccessarily stable, but std::stable_sort is.

CM

##### Share on other sites
Quote:
 Original post by BoderIs 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 on other sites
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 on other sites
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 on other sites
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.

1. 1
2. 2
Rutin
24
3. 3
4. 4
JoeJ
16
5. 5

• 14
• 29
• 11
• 11
• 9
• ### Forum Statistics

• Total Topics
631773
• Total Posts
3002265
×