Sorting 2D arrays in C/C++ in increasing values; knowing the original positon after sorting ?

Answer 1

One simple way is that instead of storing only values in your original Array2D you store a small struct:

struct {
    int value;
    int position;
};

before you sort the array you store the position in the position variable. For a complete solution try something like this:

struct Element {
    Element() {}
    Element(int value) : value(value) {}
    bool operator < (const Element& rhs) const {return value < rhs.value;}
    int value;
    int position;
};

Element Array2D[2][5];
Array2D[0][0] = 99;
Array2D[0][1] = 10;
Array2D[0][2] = 97;
Array2D[0][3] = 10;
Array2D[0][4] = 14;
Array2D[1][0] = 73;
Array2D[1][1] = 53;
Array2D[1][2] = 81;
Array2D[1][3] = 22;
Array2D[1][4] = 88;
int elementCount = sizeof(Array2D) / sizeof(Element);
for (int i = 0; i < elementCount; ++i) {
    (&Array2D[0][0])[i].position = i;
}
std::stable_sort(&Array[0][0], &Array[0][0] + elementCount);

Answer 2

Not sure if this is portable, but on my platform (VC9) I can just treat it as a 1d array and sort as normal, i.e.:

int array2d[2][5];
//fill array...

int *array = (int*)array2d;
//so  array[4] == array2d[0][4]
//and array[6] == array2d[1][1]

//sort as a 1d array using your favourite algorithm
...