How to sort the columns of a 2D vector by a specific row?-CodePudding

I have a 2D vector, and i would like to sort all its columns by a sorting a specific row (the inner vectors) like this:

input:

{{5,6,9},
 {1,7,5},
 {3,5,7}}

sorting the elements to asc in row 2, the vector would be:

{{5,9,6},
 {1,5,7},
 {3,7,5}}

CodePudding user response：

If stl sort is an acceptable choice, you can do like this:

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

using namespace std;

int main()
{
    // According to your description, the input is row major
    vector<vector<int>> vec_2d{
        {5,6,9},
        {1,7,5},
        {3,5,7} };
    // Convert the input vec to col major
    int rows = vec_2d.size();
    int cols = vec_2d.front().size();
    // Allocate a new 2d vec which stores values by col major
    vector<vector<int>> vec_2d_col_major(cols, vector<int>(rows));
    for (int i = 0; i < rows;   i) {
        for (int j = 0; j < cols;   j) {
            vec_2d_col_major[j][i] = vec_2d[i][j];
        }
    }
    // Sort by asc the 2nd row
    sort(vec_2d_col_major.begin(), vec_2d_col_major.end(), [](const vector<int>& a, vector<int>& b) {
        return a[1] < b[1];
    });
    // Copy data from col major to row major
    for (int i = 0; i < rows;   i) {
        for (int j = 0; j < cols;   j) {
            vec_2d[i][j] = vec_2d_col_major[j][i];
        }
    }
    // Check the sort result
    for (const auto& row : vec_2d) {
        for (auto num : row) {
            cout << num << " ";
        }
        cout << endl;
    }
}

Output:

5 9 6
1 5 7
3 7 5

I suppose your input vector is stored in row major by std::vector

CodePudding user response：

sorted by reorder, use a vector to keep the order for each column.

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

template<class T>
void show(const std::vector<std::vector<T>>& values) {
  for (auto& raw : values) {
    for (auto& v : raw)
      std::cout << v << " ";
    std::cout << std::endl;
  }
}

template<class T>
void swap(std::vector<std::vector<T>>& values, uint32_t i, uint32_t j) {
  for (auto& row : values)
    std::swap(row[i], row[j]);
}

template<class T>
void reorder(std::vector<std::vector<T>>& values, std::vector<uint32_t>& order) {
  for (uint32_t i = 0; i < order.size();   i) {
    while (order[i] != order[order[i]]) {
      swap(values, order[i], order[order[i]]);
      std::swap(order[i], order[order[i]]);
    }
  }
}

template<class T>
void sort_row(std::vector<std::vector<T>>& values, int32_t row) {
  uint32_t row_count = values.size();
  uint32_t col_count = values[row].size();

  std::vector<uint32_t> sorted_idx(col_count);
  for (uint32_t i = 0; i < col_count;   i)
    sorted_idx[i] = i;

  std::sort(sorted_idx.begin(), sorted_idx.end(),
      [&](uint32_t i, uint32_t j) {
        return values[row][i] < values[row][j];
      });
  reorder(values, sorted_idx);
}

int main(int, char**) {
  std::vector<std::vector<int32_t>> values = {
    {-1, -3, -2, -4},
    { 0,  1,  2,  3},
    { 5,  6,  7,  8}
  };
  sort_row(values, 0);
  show(values);
  return 0;
}