Sorting a matrix

[Stampede]

How to sort a matrix as in 4x4 like

4 4
6 1 1 2
7 2 9 4
7 3 1 5
7 2 9 3

with the following rules :

A = A(1),A(2),...,A(n) B = B(1),B(2),...,B(n) for 2 rows of the matrix and
we have to sort it like A(1)=B(1), A(2)=B(2),...,A(k)=B(k), a A(k+1)<B(k+1)

Please help me figure this out !

so that i receive this :
6 1 1 2
7 2 9 3
7 2 9 4
7 3 1 5

I'm trying to make it so that you can give it any random 4x4 matrix as in a input from file or something else.

[keskiverto]

You have a list of "items". You want to sort that list based on an "attribute" of items.

An "item" is one row of matrix.
The "attribute" is the value of the last column of the row.
Is that what you said?

[Stampede]

Yes that is what i mean.
Basically sorting in a ascending way so if A(1)=B(1), A(2)=B(2),...,A(k)=B(k), a A(k+1)<B(k+1) is true, then Row A has to be before row B in the sorted matrix and if A(k+1)>B(k+1) is true then the row B has to be before the row A

[keskiverto]

A sort relies on two operations:
* ordering. Is item A < item B? If not, adjust the list
* swap. Exchange two items

How to implement those operations? Depends on how you you have stored the data.

[Stampede]

Can you give me some example, i have no idea how exactly to do this.

[Stampede]

I wrote this :

using namespace std;
#include <algorithm>
#include <stdio.h>
#include <vector>

vector<vector<int > > matrix;
int main() {
    int n, i, j;
    vector<int> b;
    scanf("%d", &n);
    for(i = 0; i < n; i++){
        matrix.push_back(b);
    }
    for(i = 0; i < n; i++)
    {
        for(j = 0; j < n; j++) {
            int y;
            scanf("%d", &y);
            matrix[i].push_back(y);
        }
    }
     for(i = 0; i < n; i++)
    {
        for(j = 0; j < n; j++) {
            int x = matrix[i][j];
            printf("%d ", x);
                  }
            printf("\n");

    }
}

but im not sure where my mistake is.
How do i exactly implement the rules i have put about Row A and row B ?

[keskiverto]

#include <iostream>
#include <vector>
#include <algorithm>

using Row = std::vector<int>;
using Matrix = std::vector<Row>;

void print( const Matrix& data ) {
  for ( auto& row : data ) {
      for ( auto elem : row ) {
          std::cout << ' ' << elem;
      }
      std::cout << '\n';
  }
}

int main()
{
  Matrix matrix {
    {6, 1, 1, 2},
    {7, 2, 9, 4},
    {7, 3, 1, 5},
    {7, 2, 9, 3}};
  print( matrix );
  std::cout << '\n';
  std::sort( matrix.begin(), matrix.end(),
            [](Row& lhs, Row& rhs) { return lhs.back() < rhs.back(); }
           );
  print( matrix );
}

In the above the "list of items" is std::vector of Row objects.

A Row is a vector of integers. There is a method to swap two vectors. The std::sort calls that method when necessary.

We give the std::sort a nameless function:

[]( Row& lhs, Row& rhs )
{
  return lhs.back() < rhs.back();
}

That returns true if lhs should be before rhs in the sorted matrix.

[lastchance]

Are you sure that you need to look at the last element of the row? Surely the ordering is defined by the first mismatch in a row? In which case, the sorting predicate would be a bit longer.

[Stampede]

Yes i believe its proper, sadly if you enlarge the matrix it goes nuts as in 5x5 or 6x6 etc.

[lastchance]

I don't see what that has to do with the size of the matrix, @Stampede.

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

using Row = vector<double>;
using Matrix = vector<Row>;

//======================================================================


bool operator < ( const Row &a, const Row &b )        // Define ordering for rows
{
   for ( int i = 0; i < a.size(); i++ )
   {
      if ( a[i] < b[i] ) return true;
      if ( a[i] > b[i] ) return false;
   }
   return false;
}


//======================================================================


ostream &operator << ( ostream &strm, const Matrix &M )
{
   for ( auto &row : M )
   {
      for ( auto e : row ) strm << e << '\t';
      strm << '\n';
   }
   return strm;
}


//======================================================================


int main()
{
   Matrix M{  { 6, 1, 1, 2 },  { 7, 2, 9, 4 },  { 7, 3, 1, 5 },  { 7, 2, 9, 3 }  };
   cout << "Pre-sorting:\n" << M << '\n';
   sort( M.begin(), M.end() );                        // Uses defined < operator
   cout << "Post-sorting:\n" << M << '\n';
}


//====================================================================== 

Pre-sorting:
6	1	1	2	
7	2	9	4	
7	3	1	5	
7	2	9	3	

Post-sorting:
6	1	1	2	
7	2	9	3	
7	2	9	4	
7	3	1	5	

[keskiverto]

Please explain the nuts.