How to sort a 2D matrix by last column

Question

How can I sort a 2D matrix by last column using a comparable function instead of using position arrays?

4 20 15 23 18 9 89 1 8 23 22 14 18 86 17 15 13 18 12 15 90 3 18 8 20 12 5 66

This is my example of 2D matrix where the last column represents the sum of the elements of row i = 1 -> n. I have to sort the rows in ascending order comparing the elements of the last column.

EDIT!

First code was this one:

int main()
{
    int x[101][101],y[101],z[101],n,m;
    int i,I,j,l,Mi=1000001,b=0;
    int s=0;

    cin>>n>>m;

    for(i=1;i<=n;i++)
        for(I=1;I<=m;I++)
            cin>>x[i][I];
    for(i=1;i<=n;i++)
    {
        s=0;
        for(I=1;I<=m;I++)
            s=s+x[i][I];
        y[i]=s;
    }
    for(l=1;l<=n;l++)
    {
        Mi=1000001;
        for(j=1;j<=n;j++)
            if(y[j]<Mi)
            {
                Mi=y[j];
                b=j;
            }
        z[l]=b;
        y[b]=1000002;
    }

    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
            cout<<x[z[i]][j]<<" ";
        cout<<endl;
    }
    return 0;
}

But as i said..i used possition arrays which are not the best thing to use because they use a lot of space and I don't want that. The array is an integer array. I got stuck because I don't know another method that's why I wanted to reach for your help.

Answer 1

Look at this simple example. I suggest to use std::vector to store matrix. For sorting use std::sort with defined compare lambda (cmp).

#include <iostream>
using namespace std;

const int C = 5, R = 5;
using row = vector<int>;
using matr = vector<row>;

struct matrix
{
    matr m_matrix;
    matrix(int row, int col)
    {
        m_matrix.resize(row);
        for(auto &a : m_matrix)
            a.resize(col);
    }
    void set(int r, int c, int val)
    {
        m_matrix[r][c] = val;
    }
    void sort()
    {
        auto cmp = [](const row &r1, const row &r2)
        {
            return r1[r1.size() - 1] < r2[r2.size() - 1];
        };
        std::sort(m_matrix.begin(), m_matrix.end(), cmp);
    }
    void print()
    {
        for(auto &a : m_matrix)
        {
            for(auto v : a)
                cout << v << "  ";
            cout << endl;
        }
    }
};


void fill_matrix(matrix &m)
{
    int cntr = 15;
    for(int i = 0;i < C;i++)
    {
        int sum = 0;
        for(int j = 0;j < R - 1;j++)
        {
            int value = 10 + (cntr++) % 20;
            m.set(i, j, value);
            sum += value;
        }
        m.set(i, R - 1, sum);
    }
}


int main(int argc, char* argv[])
{
    matrix m(5, 5);
    fill_matrix(m);    
    m.print();
    cout << endl;
    m.sort();
    m.print();
}

Results:

Answer 2

First of all - use std::array<T, size> instead of C-style square bracket arrays (T[]). Usage:

std::array<std::array<int, 7>, 4> matrix{
        {
                {{4, 20, 15, 23, 18, 9, 89}},
                {{1, 8, 23, 22, 14, 18, 86}},
                {{17, 15, 13, 18, 12, 15, 90}},
                {{3, 18, 8, 20, 12, 5, 66}}
        }
};

While the confusing number of parentheses might look bizzare at first, you will quickly forget about it when you realise how powerful of a tool std::array is.

Second of all - use standard algorithms. You need to:

• obtain the last element of a given row
• obtain the last element of another row
• define a comparison function that would compare aforementioned elements to effectively be used to compare entire rows
• use that function with standard sorting algorithm: std::sort

Proposed solution:

std::sort(matrix.begin(), matrix.end(), [](const auto& first_row,
                                           const auto& second_row) {
    return first_row.back() < second_row.back();
});

We use a lambda expression to define a comparator that will compare two rows. That's all std::sort needs - a way to compare two elements of a range it sorts - in this case, we define how to compare two rows of a matrix (the common C++ way is to provide a strict weak ordering using less-than operator - that's why < is used to compare last elements or each row. If you wish to reverse the order, simply use >. Do not use either <= or >= though, since they do not provide strict ordering).