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

cmultidimensional-array

I have already written a program that sorts a 2D array in increasing values.

Here is my input and output.

Input:



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 



Output:



Array2D[0][0] = 10 
Array2D[0][1] = 22 
Array2D[0][2] = 53 
Array2D[0][3] = 53 
Array2D[0][4] = 73 
Array2D[1][0] = 73 
Array2D[1][1] = 81 
Array2D[1][2] = 81 
Array2D[1][3] = 88 
Array2D[1][4] = 99

Now, what I want to know is the original position of values. E.g. Array2D[0][0] contains 10 now, but I also want to know where this 10 was before in input, here in this eg, it was in Array2D[0][3] in input. So, I want to original position of all the values.

I don't have much idea how to do this. Maybe use some additional struct to remember the position or to use pointers. Any help would be appreciated.

It can be done in C,C++.

Note: for Sorting, I converted 2D array into 1D array, and sort it using bubble sort and convert back to 2D array.

Best Answer

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);
Related Topic