[C++] Sorting two dimensional array

[Action Hank]

I have two dimensional array which I would like to sort by the 2nd column.

Array consists of two columns - IDs and values.

It looks like this

1 21

2 6

3 54

4 65

5 11

... ...

and I would like to get an output like this:

4 65

3 54

1 21

5 11

2 6

I tried to follow cplusplus.com sort reference, but I can't rebuild it for my needs.

[+Majesticmerc MVC]

You could simply use a sort routine for a 1-dimensional array, but repeat each sort movement in the second "column" too, so you're only sorting on the first dimension of the array, but the "rows" stay synchronised.

[Andre S. Veteran]

If you don't feel like coding a sort routine, this can be done using temporary STL vectors:

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int arr[5][2] = { { 1, 21 }, { 2, 6 }, { 3, 54 }, { 4, 65 }, { 5, 11 } };

bool mySortFunction(const vector<int>& inner1, const vector<int>& inner2) {
	return inner1[1] < inner2[1];
}

int main() {
	vector<vector<int> > vect;
	for (int i = 0; i < 5; ++i) {
		vector<int> inner(arr[i], arr[i] + 2);
		vect.push_back(inner);
	}

	sort(vect.begin(), vect.end(), mySortFunction);

	for (int i = 0; i < 5; ++i) {
		arr[i][0] = vect[i][0];
		arr[i][1] = vect[i][1];
	}
}

Keep in mind though that this implies a lot of unnecessary memory allocation and freeing, which can slow down the process tremendously. This isn't due to the STL being inefficient (it isn't), but creating a lot of vectors on the fly can't be very fast, unless you start writing your own memory allocators, but that's starting to look uglier than coding your own sort routine.

Edited January 7, 2010 by Dr_Asik

[Argote]

Do you have any complexity targets ( O(n^2), O(n log2 n), etc. )?

[Action Hank]

Dr_Asik - it works great.

Thanks for help.