Sort 2-D Array

I want to a 2-D Array in Descending order according to the the second column and the corresponding values of the row remain the same.

e.g Arr[3][2](no of columns is constant=2)

1 5
2 8
3 3

after sorting output should be

2 8
1 5
3 3
Normally, you would be using better-behaved C++ containers, such as vectors:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <vector>
#include <algorithm>
#include <iostream>

bool compare_vectors(const std::vector<int>& lhs, const std::vector<int>& rhs)
{
    return rhs.back() < lhs.back();
}

int main()
{
    std::vector<std::vector<int>> Arr = {{1, 5},  {2, 8}, {3, 3}};

    std::sort(Arr.begin(), Arr.end(), compare_vectors);

    for(auto& row: Arr)
    {
        for(auto& n: row)
            std::cout << n << ' ';
        std::cout << '\n';
    }

}

online demo: http://ideone.com/ZNQ7G4

Same for the C++ arrays (std::array). But for C-style arrays, there's always a C way to do it:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <cstdlib>
#include <iostream>

const int COL = 2;

int compare_rows(const void* lhs, const void* rhs)
{
    auto l = static_cast<const int(*)[COL]>(lhs);
    auto r = static_cast<const int(*)[COL]>(rhs);
    return (*r)[COL-1] - (*l)[COL-1];
}

int main()
{
    int Arr[3][COL] = {{1, 5}, {2, 8}, {3, 3}};

    std::qsort(Arr, 3, sizeof Arr[0], compare_rows);

    for(auto& row: Arr)
    {
        for(auto& n: row)
            std::cout << n << ' ';
        std::cout << '\n';
    }
}

online demo: http://ideone.com/WhMqIb
Last edited on
The same as if you were sorting a 1d array, except swap an entire array.
You can not use standard C++ sort algorithms with multidimensional arrays because they require that elements of the array will be MoveAssignable. But arrays are not MoveAssignable that is there is no the assignment operator for arrays.

So you have two possibilities. Either to use C standard algorithm qsort as Cubbi showed or to write your own sort function for example some realization of the selection sort.
Last edited on
Consider using an indirect sort when one or more of the following hold:

a. We need a sorted view of an immutable sequence.
b. We need to access the sequence in two different ways - in the original order and in a sorted order
c. A sequence contains objects which are expensive to move around, but we need a sorted view.

For instance, if the dimensions of the array are not trivial, this would be handy:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <functional>
#include <algorithm>

int main()
{
    enum { NROWS = 3, NCOLS = 5, SORT_COL = 1 } ;
    typedef int row_type[NCOLS] ;
    row_type rows[NROWS] = { { 1, 5, 2, 3, 4 }, { 2, 8, 3, 4, 5 }, { 3, 3, 4, 5, 6 } } ;

    std::vector< std::reference_wrapper<row_type> > refs( std::begin(rows), std::end(rows) ) ;
    std::sort( refs.begin(), refs.end(),
               [] ( const row_type& a, const row_type& b ) { return a[SORT_COL] > b[SORT_COL] ; } ) ;

    for( const auto& r : refs )
    {
        for( int v : r.get() ) std::cout << v << ' ' ;
        std::cout << '\n' ;
    }
}



Both the Codes are giving error.
The one posted Cubbi

1
2
3
4
5
6
7
8
9
10
11
test.cpp:13:63: error: in C++98 ‘Arr’ must be initialized by constructor, not by ‘{...}’
test.cpp:13:63: error: deducing from brace-enclosed initializer list requires #include <initializer_list>
test.cpp:13:63: error: deducing from brace-enclosed initializer list requires #include <initializer_list>
test.cpp:13:63: warning: extended initializer lists only available with -std=c++0x or -std=gnu++0x
test.cpp:13:63: error: could not convert ‘{{1, 5}, {2, 8}, {3, 3}}’ to ‘std::vector<std::vector<int> >’
test.cpp:17:18: error: expected initializer before ‘:’ token
test.cpp:24:2: error: expected primary-expression before ‘return’
test.cpp:24:2: error: expected ‘;’ before ‘return’
test.cpp:24:2: error: expected primary-expression before ‘return’
test.cpp:24:2: error: expected ‘)’ before ‘return’
make: *** [test] Error 1


and the one posted by JLBorges gives:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
test.cpp:34:5: error: ‘srd’ has not been declared
test.cpp:34:18: error: ‘reference_wrapper’ is not a member of ‘std’
test.cpp:34:49: error: expected primary-expression before ‘>’ token
test.cpp:34:51: error: expected primary-expression before ‘>’ token
test.cpp:34:59: error: ‘begin’ is not a member of ‘std’
test.cpp:34:77: error: ‘end’ is not a member of ‘std’
test.cpp:34:92: error: ‘refs’ was not declared in this scope
test.cpp:36:97: warning: lambda expressions only available with -std=c++0x or -std=gnu++0x
test.cpp:38:24: error: expected initializer before ‘:’ token
test.cpp:44:2: error: expected primary-expression before ‘return’
test.cpp:44:2: error: expected ‘;’ before ‘return’
test.cpp:44:2: error: expected primary-expression before ‘return’
test.cpp:44:2: error: expected ‘)’ before ‘return
Compile with the option -std=C++11
Neither the first nor the second example will be compiled if you are using MS VC++ 2010. It does not support many new features of the C++ 2011 Standard. The first example of Cubbi can be simply updated by removing brace initialization

std::vector<std::vector<int>> Arr = {{1, 5}, {2, 8}, {3, 3}};

and using ordinary push_back method.
Last edited on
I will show how to change Cubbi's example.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <vector>
#include <algorithm>
#include <iostream>

bool inline compare_vectors(const std::vector<int>& lhs, const std::vector<int>& rhs)
{
    return rhs.back() < lhs.back();
}

int main()
{
    std::vector<std::vector<int>> Arr( 3, 2 );

    Arr[0][0] = 1; Arr[0][1] = 5;
    Arr[1][0] = 2; Arr[1][1] = 8;
    Arr[2][0] = 3; Arr[2][1] = 3;

    std::sort(Arr.begin(), Arr.end(), compare_vectors);

    for ( const auto& row: Arr )
    {
        for ( auto n: row )
            std::cout << n << ' ';
        std::cout << '\n';
    }
}
Topic archived. No new replies allowed.