Sort based on multiple things in C++

struct Record
{
    char Surname[20];
    char Initial;
    unsigned short int Gender; //0 = male | 1 = female
    unsigned short int Age;
};
Record X[100];

How can I use Quicksort to sort the values into increasing age,开发者_JS百科 with females before males and surnames in alphabetical order? I've got a:

bool CompareData(const int& A, const int& B)
{
    return Records[A].Age < Records[B].Age; //this sorts by age atm
}

the general pattern is:

bool CompareData(const T& a, const T& b) 
{ 
   if (a.PrimaryCondition < b.PrimaryCondition) return true;
   if (b.PrimaryCondition < a.PrimaryCondition) return false;

   // a=b for primary condition, go to secondary
   if (a.SecondaryCondition < b.SecondaryCondition) return true;
   if (b.SecondaryCondition < a.SecondaryCondition) return false;

   // ...

   return false;
} 

where < indicates the "less than" in the desired sort order, you might need to use custom comparison operators for that (e.g. strcmp for strings,or reverse the < if you want to order descending) (thanks Harry for pointing this out)

I've used < on all conditions, since that's sometimes the only comparison operation available, e.g. when you have to use an unknown data type's comparison predicate.

[edit] Note: the last line return false handles the case where aand bare considered equal for the comparator.

Imagine a.PrimaryCondition==b.PrimaryCondition and a.SecondaryCondition==b.SecondaryCondition - in this case, none of the previous conditions returns any value.

bool CompareData(const int& A, const int& B)
{
    return (Records[A].Age < Records[B].Age) ||
           ((Records[A].Age == Records[B].Age) && (Records[A].Gender > Records[B].Gender)) || 
           ((Records[A].Age == Records[B].Age) && (Records[A].Gender == Records[B].Gender) &&
              (strcmp(Records[A].Surname, Records[B].Surname) < 0));
}

This compares first by age and returns true if A should appear before B based on age.

If ages are equal, it then compares by gender, and returns true if A should appear before B based on gender (A is female and B is male).

If ages are equal and genders are equal, it then compares by surname (using strcmp, although if you had used std::string instead of a char array, you could have just used <), and returns true if A should appear before B alphabetically by surname.

the other option to an all singing all dancing comparator is to make sure your sort is a stable sort (quick sort isn't necessarily stable) and sort multiple times with different comparators each time.

e.g.

bool CompareAge (const record& l, const record& r)
{
  return l.age < r.age;
}

bool CompareGender (const record& l, const record& r)
{
  return l.gender < r.gender;
}

std::stable_sort(X, X+100, &CompareGender);
std::stable_sort(X, X+100, &CompareAge);

this will be potentially slightly slower but allow you more flexibility with the order of sorts

The simple C++ solution is

struct Record {
    std::string Surname;
    char Initial;
    unsigned short int Gender; //0 = male | 1 = female
    unsigned short int Age;

    operator<(Record const& rhs) const {
        return std::tie(Gender, Age, Surname) < std::tie(rhs.Gender, rhs.Age, rhs.Surname);
};

However, std::tie sorts directly on the field values. This means you can't use char[20] and males will sort first. A simple variation solves this:

struct Record {
    char Surname[20];
    char Initial;
    unsigned short int Gender; //0 = male | 1 = female
    unsigned short int Age;

    operator<(Record const& rhs) const {
        return std::make_tuple(~Gender, Age, std::string(Surname)) <
               std::make_tuple(~rhs.Gender, rhs.Age, std::string(rhs.Surname));
};

With make_tuple we can pass expressions.

It's better to implement comparator like this:

bool CompareRecords(const Record& a, const Record& b)
{
    if (a.Age < b.Age)
        return true;
    else if (a.Age > b.Age)
        return false;

    if (a.Gender < b.Gender)
        return true;
    else if (a.Gender > b.Gender)
        return false;

    if (strcmp(a.Surname, b.Surname) < 0)
        return true;

    return false;
}

This allows you to easy use of std::sort algorithm. Sorting itself will look like this:

std::sort(X, X + 100, &CompareRecords);

EDIT

You may even want to implement operator < for this structure -- in that case you can normally compare two objects of Record structure with operator <. And then you don't need to add the third parameter to std::sort. And well, with that and implemented operator == you can make all possible comparizons. :)