CODEWITHSUNDEEP
c++sortingvector
chariked
chariked

Reputation: 49

C++ Sorting multiple columns in a vector of vectors

I'm trying to sort multiple columns with my nested vector but I'm unsure on how to actually do it. I've searched a bunch of posts on here but they only show how to sort up to two columns and I know sorting one column is the following:

sort(myVector.begin(), myVector.end(), [](vector<int> const a, vector<int> const b){return a[0] < b[0];});

I have an input where the user enters the size of the vector and it generates accordingly, I want to be able to sort each column on the output.

For example:

Unsorted

{3, 7, 2}

{9, 6, 8}

{5, 1, 4}

Sorted

{3, 1, 2}

{5, 6, 4}

{9, 7, 8}

Upvotes: 0

Views: 921

Answers (1)

Rerito
Rerito

Reputation: 6086

This a classic in linear algebra libraries: the layout of a given matrix can impact a lot the performance due to the patterns of element access.

You face exactly the same outcome. Obviously each vector of int is a row in your case. You need to sort columns. What you can do is the transpose trick:

  1. Compute the transpose of your matrix
  2. Sort the rows of that transpose
  3. Compute back the transpose of this sorted matrix
  4. Profit

Some code to illustrate the idea:

std::vector<std::vector<int>> transpose(std::vector<std::vector<int>> const& input) {
    // For simplicity, I assume input is well formed, i.e.:
    //  - All int vectors have the same size
    //  - input is non-empty.
    std::vector<std::vector<int>> tr_input;
    for(std::size_t i = 0; i < input.front().size(); ++i) {
        std::vector<int> tmp;
        for (auto& vec : input) {
            tmp.push_back(vec.at(i));
        }
        tr_input.push_back(tmp);
    }
    return tr_input;
}

Now we have the transpose function, we can implement the algorithm.

std::vector<std::vector<int>> input = { { 3, 7, 2 },
                                        { 9, 6, 8 },
                                        { 5, 1, 4 } };
auto tr = transpose(input);
for (auto& v : tr) {
    std::sort(v.begin(), v.end());
}
auto sorted = transpose(tr);

The result can be viewed on this Live Demo

Upvotes: 3

Related Questions