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?






Comments and Discussions

Ad: Are you a blogger? Join our Blogging forum.





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.