Sort a 2D array in C++ using built in functions(or any other method)?
Solution 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.
Solution 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) ...
Solution 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
Solution 4
First off, if you'd given vector<vector<int>> array
this would be sortable just using: sort(begin(array), end(array))
because vector
defines lexicographic comparison functions: http://en.cppreference.com/w/cpp/container/vector/operator_cmp
That said, there are drawbacks to using a vector
-of-vector
s: What are the Issues with a vector-of-vectors? and it's clearly not what you intended. Given int array[5][2]
trying to use sort
will yield:
error C3863: array type 'int [2]' is not assignable
Instead of using swap
to exchange 2 int[2]
s we need to simply need to swap bytes of sizeof(*array)
, that can be accomplished using qsort
as suggested by WhozCraig's answer, but we can improve upon that making our comparator capable of handling any size sub-array. Given int array[5][2]
or whatever dimensions are desired we can write:
static const auto SIZE = size(*array);
qsort(array, size(array), sizeof(*array), [](const auto lhs, const auto rhs) {
const auto first = reinterpret_cast<const int*>(lhs);
const auto last = next(first, SIZE);
const auto its = mismatch(first, last, reinterpret_cast<const int*>(rhs));
if (its.first == last) {
return 0;
} else if (*its.first < *its.second) {
return -1;
} else {
return 1;
}});
A quick note array
should not be used as a variable name as it defines a standard type, with this change you can find an example here: http://ideone.com/87AoIr
Solution 5
If you can, use Vector
with some struct to hold two int
:
typedef std::pair<int, int> pairType;
std::vector<pairType> vec;
// Initialize vector
std::sort(std::begin(vec), std::end(vec), [](pairType& first, pairType& second)->bool { return first.first < second.first });
Related videos on Youtube
![prime](https://i.stack.imgur.com/ogeU4.gif?s=256&g=1)
prime
Updated on December 20, 2020Comments
-
prime over 3 years
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 :)
-
Bo M. Petersen over 10 yearsHow did you declare array[5][2]. are they just int's or did you use a STL container like std::vector, std::array ect...?
-
WhozCraig over 10 yearsAs odd as it sounds,
std::qsort()
may be an easier built-in to wedge-fit into a classic 2D array when sorting by single column. -
Christopher Creutzig over 10 years
std::sort
accepts a comparator as the third argument. Anyop
such thatop(a,b)
meansa < b
is fine – function, lambda, functor object. Due to inlining, it’s usually faster thanqsort
with the same function, too. -
SJHowe over 3 yearsI have seen the solutions and all of them transform the problem to solve it (std::array, std::vector, std::map) . Is there no way of sorting with 2d-array? After all, pointers can be iterators. Offhand I don't see a solution as the innermost dimension is an array and arrays are not assignable.arrays embedded in a struct are.
-
-
Jarod42 over 10 yearsuse
std::begin(a)
andstd::end(a)
instead ofa
anda + 5
. -
herohuyongtao over 10 yearsHow about sorting based on the second elements?
-
herohuyongtao over 10 yearsWhy the code will give
error C2664: 'qsort' : cannot convert parameter 4 from '
anonymous-namespace'::<lambda2>' to 'int (__cdecl *)(const void *,const void *)'` under VS? -
Christopher Creutzig over 10 yearsWhy do you think
std::sort(std::begin(ar), std::end(ar), [](int const (&ar)[2])->bool{…}
wouldn’t work just as well? -
pentadecagon over 10 years@herohuyongtao:
sort( a, a + 5, []( array<int, 2>& u, array<int, 2>& v ){ return u[1] < v[1]; } );
-
WhozCraig over 10 years@ChristopherCreutzig Have you tried it?
std::sort
uses move and value assignment, and fixed C arrays are not assignable by-value (though they can be initialized). So to answer the question you posed, because it wouldn't work at all, therefore it wouldn't work as well. -
WhozCraig over 10 years@herohuyongtao That would be the fault of MS, but you can get around it by moving the lambda to its own static function. the rest would be the same.
-
Christopher Creutzig over 10 years@WhozCraig No C++ on my iPad, sorry. :-) But you’re right, of course – while fixed C arrays have the minor advantage that we know their layout (in all practical situations), they don’t behave properly in the world of C++. And with any half-decent compiler, a simple
std::pair<int,int>
or custom class w/o virtuals doesn't take more space either, so there’s really little reason to use them in the first place. -
Jonathan Mee almost 8 yearsI've up-voted this answer, because I believe
qsort
is the correct answer, but I've replaced your lambda in my answer with one capable of coping with variably sized arrays: stackoverflow.com/a/38249167/2642059 -
arhuaco almost 7 yearsJust to point out that this only works if
array[i][0]
is unique (for all i). -
WhozCraig about 6 yearsNice answer. Note that most of the drawbacks of vector of vectors go away in the OP's specific case of fixed arrays with C++11 and beyond. Indeed,
std::array<std::array<int, M>, N>
withN
andM
being rows and columns respectively, would work wonderfully withstd::sort
. If the outer dimension is potentially unruly, a vector of arrays would still work well. -
Jonathan Mee about 6 years@WhozCraig Just took me 2 years to write it after reading your answer ;)