CODEWITHSUNDEEP
c++carrayssortingstructure
SuperCoder
SuperCoder

Reputation: 121

How to sort an array of structures according to values of one of its members, breaking ties on the basis of another member?

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

Upvotes: 0

Views: 2429

Answers (3)

jfly
jfly

Reputation: 7990

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

Upvotes: 2

BLUEPIXY
BLUEPIXY

Reputation: 40155

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));
}

Upvotes: 3

juanchopanza
juanchopanza

Reputation: 227468

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);
          });

Upvotes: 2

Related Questions