Sort a 2D array in C++ using built in functions(or any other method)?

Question

I have a 2D array like below. ( array[5][2] )

20  11    
10  20
39  14
29  15
22  23

after sorting it should be like below.

10  20
20  11
22  23
29  15
39  14

that means the array should be sorted comparing the first column values only.

In Java there is a built in function capability to do that. like below.

Arrays.sort(a, new Comparator<Long[]>() {

            @Override
            public int compare(Long[] o1, Long[] o2) {

                Long t1 = o1[1];
                Long p1 = o1[0];
                Long t2 = o2[1];
                Long p2 = o2[0];

                if (t1 == t2) {
                    return (p1 > p2 ? 1 : (p1 == p2 ? 0 : -1));
                } else {
                    return (t1 < t2 ? -1 : 1);
                }

            }
        });

So is there any C++ built in function capability to do these kind of stuff or how can i do this in C++ (the fastest implementation) ?

Thanks in advance :)

Answer 1

I'm offering this up only because it was one of the few things std::qsort does well that std::sort simply does not, namely sort multi-column fixed arrays: The comparator is a string of ternary statements, but should be clear enough if you stare at it long enough:

#include <iostream>
#include <random>
#include <algorithm>

int main()
{
    int ar[10][2];

    // populate with random data
    std::random_device rd;
    std::default_random_engine rng(rd());
    std::uniform_int_distribution<> dist(1,20);
    std::for_each(std::begin(ar), std::end(ar),
        [&](int (&ar)[2]){ ar[0] = dist(rng); ar[1] = dist(rng); });

    std::cout << "Before Sort..." << '\n';
    std::for_each(std::begin(ar), std::end(ar),
        [](const int(&ar)[2]) { std::cout << ar[0] << ',' << ar[1] << '\n';});

    std::qsort(ar, 10, sizeof(*ar),
        [](const void *arg1, const void *arg2)->int
        {
            int const *lhs = static_cast<int const*>(arg1);
            int const *rhs = static_cast<int const*>(arg2);
            return (lhs[0] < rhs[0]) ? -1
                :  ((rhs[0] < lhs[0]) ? 1
                :  (lhs[1] < rhs[1] ? -1
                :  ((rhs[1] < lhs[1] ? 1 : 0))));
        });

    std::cout << "After Sort..." << '\n';
    std::for_each(std::begin(ar), std::end(ar),
        [](const int(&ar)[2]) { std::cout << ar[0] << ',' << ar[1] << '\n';});

    return 0;
}

Sample Run (yours will vary, obviously)

Before Sort...
2,11
18,4
20,20
14,6
8,10
17,8
14,14
3,10
20,14
19,19
After Sort...
2,11
3,10
8,10
14,6
14,14
17,8
18,4
19,19
20,14
20,20

Notes: this specifically uses strict-value comparison rather than subtraction short-cuts in the comparator so as to avoid potential underflow issues. If that is not a problem in your restricted data-space, you could easily make that comparator significantly simpler.

Answer 2

The built-in arrays of C and C++ are very inflexible, among other things they cannot be assigned.

Your best option would be the 'array' class from the C++ standard library, at least for the inner dimension:

array<int, 2> a[5] = { { 20, 11 },
{ 10, 20 },
{ 39, 14 },
{ 29, 15 },
{ 22, 23 } };

sort( a, a + 5 );

Edit: Some more explanations.

Here we use the property of std::array that '<' by default compares them lexicographically, i.e. starts with the first element. In order to sort things differently we have to come up with an comparator object, so if you want to use the second column as sort key you have to do this:

auto comp = []( const array<int, 2>& u, const array<int, 2>& v )
      { return u[1] < v[1]; };
sort( a, a + 5, comp );

And as mentioned in the first comment, sort(a, a+5 ... is just an ugly short form for the cleaner sort(std::begin(a), std::end(a) ...

Answer 3

To be honest, since you have only two ints in your second dimension, I would use instead an array of pairs, which have their own built in comparison function. With something like pair<int,int> arr[200], you would be able to call the built in sort function sort(arr, arr + 200), which would sort your array by first element, and then by the second element.

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    // pair of integers
    pair<int, int> arr[1000];

    // fill array with random numbers
    random_device rd;
    mt19937 rng(rd());
    uniform_int_distribution<int> uni(0,1000);
    for(int i = 0; i < 10; i++) {
        // make_pair(x, y) creates a pair with two integers x and y
        arr[i] = make_pair(uni(rng), uni(rng));
    }

    // prints out initial array
    cout << "BEFORE ARRAY..." << endl;
    for(int i = 0; i < 10; i++) {
        // .first and .second call the first and second ints in the pair respectively
        cout << arr[i].first << " " << arr[i].second << endl;
    }
    cout << endl;

    // sort the array by calling built in sort function
    sort(arr, arr + 10);

    // prints out array
    cout << "FINAL ARRAY..." << endl;
    for(int i = 0; i < 10; i++) {
        cout << arr[i].first << " " << arr[i].second << endl;
    }
    cout<<endl;
}

When you run this program, you see that the arrays are now sorted:

BEFORE ARRAY...
726 562
916 348
594 6
515 872
976 960
662 169
529 317
789 702
74 255
330 574

FINAL ARRAY...
74 255
330 574
515 872
529 317
594 6
662 169
726 562
789 702
916 348
976 960

Note how the second elements are also sorted, but secondary to the