sort entire 2d vector on the basis of a certain row

Question

I am interested to sort the entire 2d vector on the basis of second row. I tried some code which sort only second row, however, i want it for the entire 2d vector.

#include<iostream>
#include<vector> 
#include<algorithm> 
int main()
{
    std::vector< std::vector<int> > vect{{3, 5, 1},
                                         {4, 8, 6},
                                         {7, 2, 9}};
    int m = vect.size();
    int n = vect[0].size();
    sort(vect[1].begin(), vect[1].end());
    std::cout << "After sorting :\n";
    for (int i=0; i<m; i++)
    {
        for (int j=0; j<n ;j++)
            std::cout << vect[i][j] << " ";
        std::cout << std::endl;
    }
    return 0;
}

The output come like:

3 5 1 
4 6 8 
7 2 9 

But I want it to be

3 1 5
4 6 8
7 9 2

Answer 1

Create a function which transposes the vector, so it should modify {{3, 5, 1}, {4, 8, 6}, {7, 2, 9}} into {{3,4,7},{5,8,2},{1,6,9}}. Transpose the vector with your function, then sort the vector with custom comparator comparing the second elements of rows. Then call the transpose function again.

The transpose function could look like

std::vector< std::vector<int> > transpose(std::vector< std::vector<int> >& vect)
{
 std::vector< std::vector<int> > transposed(vect[0].size(), std::vector<int>());
 for (size_t i = 0; i < vect.size(); ++i)
  for (size_t j = 0; j < vect[0].size(); ++j)
    transposed[j].push_back(vect[i][j]);
 return transposed;
}

Then the entire code would be

vect = transpose(vect);                                     
std::sort(vect.begin(), vect.end(), 
  [](const std::vector<int>& lhs, const std::vector<int>& rhs)
     {return lhs[1] < rhs[1];});                                     
vect = transpose(vect);                                     

If a vector is square then the transposition can be done in place making the solution much more effective then this general one.

Answer 2

This code is very dirty. but exactly is the same code you want.

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

std::vector< std::vector<int> > vect = { {3, 5, 1}, {4, 8, 6}, {7, 2, 9} };

int findInVector(std::vector<int> input, int temp)
{
    for(int i=0;i<input.size();i++)
    {
        if(input[i] == temp)
        {
            return i;
        }
    }
}

bool myfunction (int i,int j)
{

    bool ret;

    if(i<j)
    {
        int i_pos = findInVector( vect[1], i);
        int j_pos = findInVector( vect[1], j);

        int temp  = vect[0][i_pos];
        vect[0][i_pos] = vect[0][j_pos];
        vect[0][j_pos] = temp;

        temp  = vect[2][i_pos];
        vect[2][i_pos] = vect[2][j_pos];
        vect[2][j_pos] = temp;

        ret = true;
    }
    else
    {
        ret = false;
    }

    return ret;
}

int main()
{
    int m = vect.size();
    int n = vect[0].size();
    sort(vect[1].begin(), vect[1].end(), myfunction);
    std::cout << "After sorting :\n";
    for (int i=0; i<m; i++)
    {
        for (int j=0; j<n ;j++)
            std::cout << vect[i][j] << " ";
        std::cout << std::endl;
    }
    return 0;
}

Answer 3

You could make an std::vector of std::pair<int,int> where in the first variable of the i-th element of the vector you have the i-th value of the second row while in the second variable you have the value of the index i.

Then you sort that vector based on the first values of the pairs. That way you can make a new 2D vector where in every row you order the elements based on the second value of the pairs, which are the old indices.

std::vector< std::vector<int> > vect{{ 3, 5, 1 },{ 4, 8, 6 },{ 7, 2, 9 }};
std::vector<std::pair<int, int>> row;

for (int i = 0; i < vect[1].size(); ++i){
    row.push_back({vect[1][i],i});
}
sort(row.begin(), row.end());

std::vector< std::vector<int> > sorted;
std::vector<int> sortedRow;
for (int i = 0; i < vect.size(); ++i){
    for (int j = 0; j < vect[i].size(); ++j){
        sortedRow.push_back(vect[i][row[j].second]);
    }
    sorted.push_back(sortedRow);
    sortedRow.clear();
}

You have to #include <utility>.

Answer 4

The structure of question won't allow us to use built-in sort function. Because, custom sort will only provides "rows". And you can compare "rows" only.

But there are some alternative ways to accomplish that.

For example you can do that by transposing vector of vector.

"Transpose > Sort by column > Transpose" may solve your problem.

But my solution is based on another dynamic.

1. Sort nth column and keep indexes as array. (n is the position of ordered row)
2. Using the array defined at step 1, sort all rows one by one.

http://cpp.sh/4dkzg

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

using namespace std;

template <typename T>
vector<size_t> sort_indexes(const vector<T> &v) {

  // initialize original index locations
  vector<size_t> idx(v.size());
  iota(idx.begin(), idx.end(), 0);

  // sort indexes based on comparing values in v
  sort(idx.begin(), idx.end(),
       [&v](size_t i1, size_t i2) {return v[i1] < v[i2];});

  return idx;
}

int main()
{
    std::vector< std::vector<int> > vect{{3, 5, 1, 2},
                                         {4, 8, 6, 1},
                                         {7, 2, 9, 5}};
    int m = vect.size();
    int n = vect[0].size();

    int sortByRow = 1; // starts from 0, if 1 => order by using 2nd row.

    /* generate reference for our actual sort operation */
    std::vector<size_t> indexSort = sort_indexes(vect[sortByRow]);

    /* sort each row using our reference vector */
    for (int i=0; i<m; i++)
    {      
        int temp[n];
        for (int j=0; j<n; j++)
            temp[j] = vect[i][indexSort[j]];

        // Copy back temp[] to vector
        for (int j=0; j<n; j++)
            vect[i][j]  = temp[j];

    }

    std::cout << "After sorting :\n";
    for (int i=0; i<m; i++)
    {
        for (int j=0; j<n ;j++)
            std::cout << vect[i][j] << " ";
        std::cout << std::endl;
    }
    return 0;
}

http://www.geeksforgeeks.org/reorder-a-array-according-to-given-indexes/ (if you want to apply in-place sorting, there are some fixes)