CODEWITHSUNDEEP
c++sortingmultidimensional-array
codepro
codepro

Reputation: 13

sorting two dimensional arrays in C++

Suppose I have a 2-d array a[4][2] like this:

1 4
2 3
3 2
4 1

I would like to sort the arrays in this array in increasing order of their second numbers, i.e. after the sorting, I would like the array to be like this:

4 1
3 2
2 3
1 4

I thought of making a map which stores the indices of the numbers in the second columns, and then making an array of the numbers in the second column and sorting that array, then reconstructing the array from the new order of the second column and the map. The problem, however, is that two numbers in the second column might not be distinct, so if a number i appears twice, map[i] will only store its last index. Also, manually checking the positions of the first numbers corresponding to the second numbers will take O(n^2) time. I want to do it in O(n log n). Does anyone have any suggestions? Is there any built in method for this (C++ 4.3.2 / 4.8.1)?

Thanks in advance.

Upvotes: 1

Views: 936

Answers (2)

Goz
Goz

Reputation: 62333

You can easily do this with std::sort. You'll need to supply a custom comparator but thats not a problem.

Its much easier if you use std::array to define your 2 dimensional array though as follows:

std::array< std::array< int, 2 >, 4 > twoDArray;

You can then sort it as follows:

std::sort( twoDArray.begin(), twoDArray.end(), []( const std::array< int, 2 >& a, const std::array< int, 2 >& b )
{
    return a[1] < b[1];
}

Doing the same with a C-style array is still possible but would require an implementation of a custom iterator that advances a whole "row" at a time as a standard iterator (ie a pointer) would treat the 2D array as if it was 1D.

Here is a full example using C++ arrays:

std::array< std::array< int, 2 >, 4 > arr   = {{ { 1, 4 },
                                                 { 2, 3 },
                                                 { 3, 2 },
                                                 { 4, 1 } }};

std::sort( arr.begin(), arr.end(), []( const std::array< int, 2 >& a, const std::array< int, 2 >& b )
    {
        return a[0] < b[0];
    } );

std::sort( arr.begin(), arr.end(), []( const std::array< int, 2 >& a, const std::array< int, 2 >& b )
    {
        return a[1] < b[1];
    } );

Upvotes: 3

Jakub Arnold
Jakub Arnold

Reputation: 87260

You can sort them once by the first item, and them sort them again using the second column. This is similar to the way radix sort would work.

Upvotes: 0

Related Questions