c++ 2D array row sort based on average row value

Helo,

I'm wondering if there's any working method for this? I'm trying make this work, but no luck.

int mat[3][3];

    mat[0][0] = 4;mat[0][1] = 5;mat[0][2] = 3;

    mat[1][0] = 3;mat[1][1] = 2;mat[1][2]开发者_StackOverflow = 1;

    mat[2][0] = 1;mat[2][1] = 8;mat[2][2] = 9;

Any idea? :)

A more idiomatically C++ way of doing this (vs. your original approach of array-of-arrays) would be to have a vector of vectors, ie. std::vector<std::vector<int> > and then invoke std::sort on the top-level vector. You can pass sort a custom predicate that compares two rows based on their average.

You should create a temporary data structure that is an array of tuples. The tuples would be the row index and the average of that row index. Then sort this tuple array based on the average using the standard sort() function. Then, run through the sorted tuple array to recompute the sorted matrix.

This would give you performance benefit of not copying the matrix rows during the swap done by the sort routine. If you only have 3 elements in your row, you may be okay with swap the whole row. But as you increase the number of columns the swapping would be become a bottleneck.

In 'pseudo code' you may do something like this:

function sort(input, numrows, numcols)
{
    pair<int, int> index[numrows];

    for (int i=0 to numrows) {
      index[i].second = i;
      // compute average of row[i] in the input matrix
      index[i].first = average_of_row(&input[i]);
    }

    // STL sort will sort the pair based on the average (.first member)
    sort(index.begin(), index.end());

    for (int i=0 to index.size())
    {
       // copy rows from input matrix to output matrix
       copy_row(&input[index[i].second], &output_matrix[i]);
    }

    return output;
}

Following @Peter's suggestion,

#include <algorithm>
#include <numeric>
#include <vector>
using namespace std;

bool comp(vector<int> a, vector<int> b) {
    if (a.size() == 0 || b.size() == 0) return false;
    int sum_a = accumulate(a.begin(), a.end(), 0);
    int sum_b = accumulate(b.begin(), b.end(), 0);
    return sum_a / (double)a.size() < sum_b / (double)b.size();
}

int main() {
    vector<vector<int> > mat(3, vector<int>(3));
    mat[0][0] = 4; mat[0][1] = 5; mat[0][2] = 3;
    mat[1][0] = 3; mat[1][1] = 2; mat[1][2] = 1;
    mat[2][0] = 1; mat[2][1] = 8; mat[2][2] = 9;
    sort(mat.begin(), mat.end(), comp);
    return 0;
}

I wasn't sure of the best way to handle empty vectors, so I just had it return false. Of course you could give comp() a more meaningful name.

EDIT: I think a better way to handle zero-sized vectors is to multiply,

bool comp(vector<int> a, vector<int> b) {
    int sum_a = accumulate(a.begin(), a.end(), 0);
    int sum_b = accumulate(b.begin(), b.end(), 0);
    return sum_a * b.size() < sum_b * a.size();
}

Put the rows in a multiset and overload the < operator. Here's a 1D example:

http://bytes.com/topic/c/answers/171028-multiset-example