tags:

views:

114

answers:

4
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, 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
}
+3  A: 
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.

Tyler McHenry
Thanks :) This really helped.
Johnny
+4  A: 

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.

peterchen
But be aware that the logical `<` relation may not always map to the `<` operator. For example, comparing the genders by `<` will be backwards, since females should appear before males, and the female value is larger, so for gender it must be `>`. And because the surnames are C-strings, the `<` operator applied to the surname field would not give a lexicographic ordering. Something like `strcmp` must be used instead.
Tyler McHenry
@Tyler: If you want to reverse the order, you exchange `return true;` and `return false;` You do not start using `operator >` because, as peterchen says, the practice established by the C++ standard algorithms library is that orderings are defined by `<` and only `<`.
Ben Voigt
@ben: I've added that together with the other clarification after Tyler's reply.
peterchen
+3  A: 

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. :)

Archie
So std::sort is better than using my own Quicksort?
Johnny
Yes, `std::sort` is better solution -- as long as you don't want to lern how to implement Quicksort itself. But in that case sorting structures like that is not a good idea. ;)
Archie
@Johnny `std::sort` is better than your own quicksort mainly because you don't have to write it. Unless the point of what you're programming is to teach yourself sorting algorithms, you should generally use what already exists.
Tyler McHenry
But my CompareData returns bool
Johnny
Tyler McHenry
ah ok, so I need a function that compares elements? Not sorting an array of Indexes?
Johnny
+2  A: 

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

jk
But Quicksort is *not* stable. (After your edit) As I said, `std::sort` is not stable; you should use `std::stable_sort` instead.
Archie
it can be. depends on the implementation
jk
Answer depending on implementation is not a good answer at all. ;)
Archie
std::sort is also not guaranteed to be stable -> changed to stable_sort
jk
This is the best answer.
DanDan
technically quick sort can be stable depending on how you pick the pivot, its just the stable implementations aren't usually used as they are slower. as the OP was implementing their own quick sort i thought it best not to presume
jk