How to sort an array of structures according to va

问题:

Suppose there is a structure:

struct x
{

int a,b,c;

};

The array of structure contains arr[0]={4,2,5}, arr[1]={6,3,1}, arr[2]={4,1,8}

then how can we sort this array in ascending order depending on value of member 'a',. tie will be broken according to value of member 'b'.

So array after sorting should be : arr[2],then arr[0], then arr[1].

I have used qsort(arr,n,sizeof(struct x),compare);

with compare function defined as

int compare(const void* a, const void * b)
{

return (*(int*)a-*(int*)b);



}

What modification I hav to do if I have to break ties acccording to member b.(currently it is breaking ties on first come first serve basis).

回答1:

int compare(const void* a, const void * b){
    struct x x = *(struct x*)a;
    struct x y = *(struct x*)b;

    return x.a < y.a ? -1 : (x.a > y.a ? 1 : (x.b < y.b ? -1 : x.b > y.b));
}

回答2:

If you are using C instead of C++, it can be done by this compare():

int compare(const void* a, const void* b) {
    struct x s_a = *((struct x*)a);
    struct x s_b = *((struct x*)b);
    if(s_a.a == s_b.a)
        return s_a.b < s_b.b ? -1 : 1; //the order of equivalent elements is undefined in qsort() of stdlib, so it doesn't matter to return 1 directly.

    return s_a.a < s_b.a ? -1 : 1;
}

If you want to break ties according to member c when member a and b are both equal, add more if-else statements in compare().

回答3:

Use std::sort with an appropriate comparator. This example uses std::tie to implement a lexicographical comparison using a first and then b, but you can write your own by hand. The only requirement is that it satisfy a strict weak ordering:

bool cmp(const x& lhs, const x& rhs)
{
  return std::tie(lhs.a, lhs.b) < std::tie(rhs.a, rhs.b);
}

std::sort(std::begin(arr), std::end(arr), cmp);

or use a lambda:

std::sort(std::begin(arr), 
          std::end(arr),
          [](const x& lhs, const x& rhs)
          {
            return std::tie(lhs.a, lhs.b) < std::tie(rhs.a, rhs.b);
          });