sort 2-d array using stl sort()

Question

I have a 2-d array, containing only 0 or 1. I want to sort it in descend order on rows (no change on each column) using STL sort algorithm. but I don't know how to pass the parameter and how to write the compare function in sort(first, last, comp); like:

0 1 1 1
1 1 0 1
1 0 1 0

would be sorted like this:

1 1 0 1
1 0 1 0
0 1 1 1

my data structure is like this:

int **table = 0;
table = new int *[row];
for(int i=0;i<row;i++)
table[i] = new int[column];

I can only write the sort function like this:

sort(a[0], a[0]+row, compare_function);

bool compare_function(int a[], int b[])
{
    int i =0;
    while(a[i]==0 ||a[i]==1)
    {
        if(a[i]>b[i])
            return true;
        else
            i++;
    }
    return false;
}

But it doesn't work. Can some one help me? Thank you very much.

Is this not ALWAYS true? `[i]==0 ||a[i]==1` (aside from when you read outside the defined area of your array, in which case the content is completely undefined - there could be a gazzilion zeros in a row before you get to a place in memory that causes your program to crash!) — Mats Petersson, Dec 21 '12 at 21:32

score 0 · Answer 1 · answered Dec 21 '12 at 21:01

0

Change your compare function to:

bool comp(const int a[], const int b[]){
  int sum1 = std::accumulate(a, a + column, 0);
  int sum2 = std::accumulate(b, b + column, 0);
  return sum1 < sum2;
}

answered Dec 21 '12 at 21:01

dchhetri

6,926
4
43
56

That doesn't give descending order, nor does it sort lexicographically (based on his example it's what he wants) – Sumudu Fernando Dec 21 '12 at 21:50
You're right. Although I can invert the comparison to give descending order, it does not necessarily sort lexicographically – dchhetri Dec 21 '12 at 22:39

score 0 · Accepted Answer · answered Dec 21 '12 at 21:49

Your call to sort looks wrong to me (though you never said what a is). It should be sort(table, table+row, compare_function)

But I'd do it a bit differently anyway (std::lexicographical_compare comes from <algorithm>):

struct compare_rows {
  const int cols;
  compare_rows(int cols_) : cols(cols_) {}
  bool operator()(const int a[], const int b[]) const {
    // a b reversed to give descending sort
    return lexicographical_compare(b, b+cols, a, a+cols);
    }
  };

And use it like:

sort(table, table+row, compare_rows(column))

sort 2-d array using stl sort()

2 Answers2

Linked