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

Question

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

 20 11 10 20 39 14 29 15 22 23 

after sorting it should look like this.

 10 20 20 11 22 23 29 15 39 14 

this means that the array should be sorted by comparing only the values ​​of the first column.

Java has a built-in function for this. as shown 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 a built-in C ++ function to create these kinds of things, or how can I do this in C ++ (the fastest implementation)?

Thank you in advance:)

Answer 1

I suggest this only because it was one of the few things that std::qsort does well, that std::sort just does not, namely, it sorts multi-table fixed arrays: the comparator is a string of ternary operators, but should be clear enough if you look 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; } 

Run example (yours will be different, 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 string comparison rather than subtracting short cuts in the comparator to avoid potential flow problems. If this is not a problem in your limited data space, you can easily make this comparator much simpler.

Answer 2

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

Your best option is the 'array' class from the C ++ standard library, at least for the internal dimension:

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

Edit: A few more explanations.

Here we use the std :: array property, which '<' compares them lexicographically by default, i.e. starts with the first element. To sort things out differently, we have to come up with a comparator object, so if you want to use the second column as a 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

If you can, use Vector with some structure to store 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 }); 

Answer 4

Honestly, since you only have two ints in the second dimension, I would instead use an array of pairs that have their own built-in comparison function. With something like pair<int,int> arr[200] you could call the built-in sort function sort(arr, arr + 200) , which would sort your array by the 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 will 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 other elements are sorted, but secondary to

Answer 5

If the end container doesn't matter, how about using a card?

 #include<map> std::map<int, int> m; for(std::size_t i = 0; i < 5; ++i ) m[array[i][0]] = array[i][1] ; 

Now you can copy m back to array

 std::size_t i=0; for(const auto& x:m) { array[i][0] = x.first ; array[i++][1] = x.second ; } 

Answer 6

The fastest way to sort a 2D array by time (using only columns).,. will cost you the link locale ... Else, every other path will include many copies of the lines ... Although (C ++ move operations can soften this)

You will create a new array of pointers to a 2D array ... Then sort the pointers ...

Otherwise, every other answer to mine seems good. But I advise you to use std :: array.

Answer 7

First of all, if you gave a vector<vector<int>> array , it would be sortable, just using: sort(begin(array), end(array)) , because vector defines the functions of lexicographic comparison: http: // en .cppreference.com / w / cpp / container / vector / operator_cmp

However, there are drawbacks to using vector -of- vector s: What are the problems with vector vectors? and this is clearly not what you intended. Given an int array[5][2] trying to use sort , you get:

error C3863: array type 'int [2]' is not assigned

Instead of using swap to exchange 2 int[2] we just need to replace the sizeof(*array) bytes that can be executed with qsort , as suggested by WhozCraig's answer , but we can improve this by making our comparator able to handle any size submatrices . Given an int array[5][2] or any other sizes, 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; }}); 

The quick note array should not be used as a variable name, since it defines a standard type, with this change you can find an example here: <a5>