ADVERTISEMENT
ADVERTISEMENT

Sort a 2D vector in C++

C++ STL | Sorting a 2D Vector: In this article, we are going to discuss how to sort a 2D vector-based on many use cases with examples?
Submitted by Radib Kar, on July 09, 2020

As per as a 2D vector is concerned it's a vector of a 1D vector. But what we do in sorting a 1D vector like,

sort(vector.begin(),vector.end());

We can't do the same for a 2D vector without any user-defined comparator function, as it will merely sort based on the first element of each column.

But we can sort 2D vector based on use cases:

1) Sort based on a particular row

The below example sorts a particular row in the 2D vector.

Say for example, the 2D matrix is:

[[3, 5, 4],
[6, 4, 2],
[1, 7, 3]]

So if we sort the first row in ascending order the output will be:

[[3, 4, 5],
[6, 4, 2],
[1, 7, 3]]
#include <bits/stdc++.h>
using namespace std;

void print(vector<vector<int> > two_D_vector)
{
    for (auto it : two_D_vector) {
        //it is now an 1D vector
        for (auto ij : it) {
            cout << ij << " ";
        }
        cout << endl;
    }
}

int main()
{
    //2D vector initialized with 
    //user-defined elements only
    vector<vector<int> > two_D_vector{
        { 3, 5, 4 },
        { 6, 4, 2 },
        { 1, 7, 3 }
    };

    //printing the 2D vector
    cout << "printing the 2D vector before sorting\n";
    print(two_D_vector);

    //sorting the 2D array based on a particular row
    //here we sort the first row of the 2D vector
    //so, basically we sort the 1D array(the first row)
    sort(two_D_vector[0].begin(), two_D_vector[0].end());

    //print the 2D vector
    cout << "printing the 2D vector after sorting\n";

    print(two_D_vector);

    return 0;
}

Output:

printing the 2D vector before sorting
3 5 4
6 4 2
1 7 3
printing the 2D vector after sorting
3 4 5
6 4 2
1 7 3

So if we sort the first row in descending order the output will be:

[[3, 5, 4],
[6, 4, 2],
[7, 3, 1]]
#include <bits/stdc++.h>
using namespace std;

void print(vector<vector<int> > two_D_vector)
{
    for (auto it : two_D_vector) {
        //it is now an 1D vector
        for (auto ij : it) {
            cout << ij << " ";
        }
        cout << endl;
    }
}

int main()
{
    //2D vector initialized with 
    //user-defined elements only
    vector<vector<int> > two_D_vector{
        { 3, 5, 4 },
        { 6, 4, 2 },
        { 1, 7, 3 }
    };

    //printing the 2D vector
    cout << "printing the 2D vector before sorting\n";
    print(two_D_vector);

    //sorting the 2D array based on a particular row
    //here we sort the last row of the 2D vector 
    //in descending order
    //so, basically we sort the 1D array in 
    //descending order(the last row)
    sort(two_D_vector[2].begin(), two_D_vector[2].end(), greater<int>());

    //print the 2D vector
    cout << "printing the 2D vector after sorting\n";

    print(two_D_vector);

    return 0;
}

Output:

printing the 2D vector before sorting
3 5 4
6 4 2
1 7 3
printing the 2D vector after sorting
3 5 4
6 4 2
7 3 1

2) Sort based on a particular column

The below example sorts a particular column in the 2D vector.

Say for example, the 2D matrix is:

[[3, 5, 4],
[6, 4, 2],
[1, 7, 3]]

So if we sort the first column in ascending order the output will be:

[[1, 4, 5],
[3, 4, 2],
[6, 7, 3]]

Here we need to define our user-defined comparator function to do the above thing. Like we will take each element of the 2D vector (which is a 1D vector, to be specific each row) and compare based on the first element (or any particular element) only. That's why we need a user-defined comparator.

#include <bits/stdc++.h>
using namespace std;

void print(vector<vector<int> > two_D_vector)
{
    for (auto it : two_D_vector) {
        //it is now an 1D vector
        for (auto ij : it) {
            cout << ij << " ";
        }
        cout << endl;
    }
}

bool mycomp(vector<int>& A, vector<int>& B)
{
    //if first element of first 
    //row<first element of second row
    if (A[0] < B[0])
        return true; //no swap
    //other wise swap the rows
    return false;
}

int main()
{
    //2D vector initialized with 
    //user-defined elements only
    vector<vector<int> > two_D_vector{
        { 3, 5, 4 },
        { 6, 4, 2 },
        { 1, 7, 3 }
    };

    //printing the 2D vector
    cout << "printing the 2D vector before sorting\n";
    print(two_D_vector);

    //sorting the 2D array based on a particular row
    //here we sort the last row of the 2D vector 
    //in descending order
    //so, basically we sort the 1D array in 
    //descending order(the last row)
    sort(two_D_vector.begin(), two_D_vector.end(), mycomp);

    //print the 2D vector
    cout << "printing the 2D vector after sorting\n";

    print(two_D_vector);

    return 0;
}

Output:

printing the 2D vector before sorting
3 5 4
6 4 2
1 7 3
printing the 2D vector after sorting
1 7 3
3 5 4
6 4 2

To sort in descending order, we need to just change the comparator function.

#include <bits/stdc++.h>
using namespace std;

void print(vector<vector<int> > two_D_vector)
{
    for (auto it : two_D_vector) {
        //it is now an 1D vector
        for (auto ij : it) {
            cout << ij << " ";
        }
        cout << endl;
    }
}
//to sort based on column in descending order
bool mycomp(vector<int>& A, vector<int>& B)
{
    //if first element of first 
    //row<first element of second row
    if (A[0] < B[0])
        return false; //swap the rows
    //other wise  no swap
    return true;
}

int main()
{
    //2D vector initialized with 
    //user-defined elements only
    vector<vector<int> > two_D_vector{
        { 3, 5, 4 },
        { 6, 4, 2 },
        { 1, 7, 3 }
    };

    //printing the 2D vector
    cout << "printing the 2D vector before sorting\n";
    print(two_D_vector);

    //sorting the 2D array based on a particular row
    //here we sort the last row of the 2D vector 
    //in descending order
    //so, basically we sort the 1D array in 
    //descending order(the last row)
    sort(two_D_vector.begin(), two_D_vector.end(), mycomp);

    //print the 2D vector
    cout << "printing the 2D vector after sorting\n";
    print(two_D_vector);
    
    return 0;
}

Output:

printing the 2D vector before sorting
3 5 4
6 4 2
1 7 3
printing the 2D vector after sorting
6 4 2
3 5 4
1 7 3

There can be various use cases to sort a 2D vector and we need to write our comparator functions.

Exercises

(a) Sort based on row sizes in ascending order

Say the 2D vector is
{
{2, 3, 4, 5},
{3, 4, 1},
{1}}

After sorting the 2D vector based on 
row size in ascending order:
{
{1},
{3, 4, 1},
{2, 3, 4, 5}
}

Here we need to use our user define a function which will swap the rows as per their sizes.

#include <bits/stdc++.h>
using namespace std;

void print(vector<vector<int> > two_D_vector)
{
    for (auto it : two_D_vector) {
        //it is now an 1D vector
        for (auto ij : it) {
            cout << ij << " ";
        }
        cout << endl;
    }
}

//to sort based on column in descending order
bool mycomp(vector<int>& A, vector<int>& B)
{
    //if first row size>second row size
    if (A.size() > B.size())
        return false; //swap the rows
    //other wise  no swap
    return true;
}

int main()
{
    //2D vector initialized with 
    //use- defined elements only
    vector<vector<int> > two_D_vector{
        { 2, 3, 4, 5 },
        { 3, 4, 1 },
        { 1 }
    };

    //printing the 2D vector
    cout << "printing the 2D vector before sorting\n";
    print(two_D_vector);

    //sorting the 2D array based on a particular row
    //here we sort the last row of the 2D vector 
    //in descending order
    //so, basically we sort the 1D array in 
    //descending order(the last row)
    sort(two_D_vector.begin(), two_D_vector.end(), mycomp);

    //print the 2D vector
    cout << "printing the 2D vector after sorting\n";

    print(two_D_vector);

    return 0;
}

Output:

printing the 2D vector before sorting
2 3 4 5
3 4 1
1
printing the 2D vector after sorting
1
3 4 1
2 3 4 5

(b) Can you sort based on column size anyway?

If you can't sort in that way, then do comment why you cant?

ADVERTISEMENT


ADVERTISEMENT


Comments and Discussions!



ADVERTISEMENT

ADVERTISEMENT

ADVERTISEMENT

ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT

Languages: » C » C++ » C++ STL » Java » Data Structure » C#.Net » Android » Kotlin » SQL
Web Technologies: » PHP » Python » JavaScript » CSS » Ajax » Node.js » Web programming/HTML
Solved programs: » C » C++ » DS » Java » C#
Aptitude que. & ans.: » C » C++ » Java » DBMS
Interview que. & ans.: » C » Embedded C » Java » SEO » HR
CS Subjects: » CS Basics » O.S. » Networks » DBMS » Embedded Systems » Cloud Computing
» Machine learning » CS Organizations » Linux » DOS
More: » Articles » Puzzles » News/Updates

© https://www.includehelp.com some rights reserved.