Сортировка на основе нескольких вещей в C ++
struct Record
{
char Surname[20];
char Initial;
unsigned short int Gender; //0 = male | 1 = female
unsigned short int Age;
};
Record X[100];
Как я могу использовать Quicksort для сортировки значений по возрасту с женщинами перед мужчинами и фамилиями в алфавитном порядке? У меня есть:
bool CompareData(const int& A, const int& B)
{
return Records[A].Age < Records[B].Age; //this sorts by age atm
}
4 ответа
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));
}
Сначала сравнение age и возвращает true, если A должен стоять перед B в зависимости от возраста.
Если возраст одинаковый, он затем сравнивает по полу и возвращает true, если A должен стоять перед B в зависимости от пола (A — женский, а B — мужской).
Если возраст и пол равны, то сравнение выполняется по фамилии (с использованием strcmp, хотя, если бы вы использовали std::string вместо массива символов, вы могли бы только что использовали <), и возвращает true, если A должен стоять перед B в алфавитном порядке по фамилии.
Лучше реализовать компаратор следующим образом:
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;
}
Это позволяет легко использовать алгоритм std::sort. Сама сортировка будет выглядеть так:
std::sort(X, X + 100, &CompareRecords);
EDIT
Возможно, вы даже захотите реализовать оператор < для этой структуры -- в этом случае вы обычно можете сравнить два объекта Record структура с оператором <. И тогда вам не нужно добавлять третий параметр в std::sort. И хорошо, с этим и реализованным operator == вы можете сделать все возможные сравнения. :)
общий шаблон:
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;
}
где < указывает «меньше чем» в желаемом порядке сортировки, вам может потребоваться использовать для этого пользовательские операторы сравнения (например, strcmp для строк или переверните <, если вы хотите упорядочить по убыванию) (спасибо Гарри за указание на это)
Я использовал < на все условия, поскольку иногда это единственная доступная операция сравнения, например когда вам нужно использовать предикат сравнения неизвестного типа данных.
[edit] Примечание: последняя строка return false обрабатывает случай, когда a и b считаются равными для компаратора.
Представьте a.PrimaryCondition==b.PrimaryCondition и a.SecondaryCondition==b.SecondaryCondition — в этом случае ни одно из предыдущих условий не возвращает никакого значения.
другой вариант компаратора "все поющие все танцующие" состоит в том, чтобы убедиться, что ваша сортировка стабильна (быстрая сортировка не обязательно стабильна) и сортировать каждый раз несколько раз с разными компараторами.
напр.
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);
это будет потенциально немного медленнее, но даст вам больше гибкости в порядке сортировки