Sorting an array

general
,
1

I have come across a problem in which my solution involves sorting an array according to some given criteria. I have an array which has some numbers and another array which just has numbers from 0 to n; arrays are of same size; and i want to sort the second array in descending order of the first array elements. To make it simple, i want to sort the first array n descending order and at the same time keep track of the indices. For ex,
int[] a = {5, 20, 10, 15}
int[] b = {0, 1, 2, 3}
If we sort ‘a’ in descending order, it would be {20, 15, 10, 5}
So, the needed array is {1, 3, 2, 0} (Sorting ‘b’ in descending order of elements of ‘a’)

I tried using Arrays.sort() but it is giving a compilation error.
Please help

2

you can use a pair to store {ele, index} in a vector/array and then sort it using the first element of pair, this way you will maintain the original index of the element in sorted form.
here is a code snippet to in C++ to get a better idea of it:

int main(){
    vector<int> a = {5, 20, 10, 15};
    vector<pair<int, int>> b;
    for(int i = 0; i < a.size(); i++)
        b.push_back({a[i], i});
    sort(begin(b), end(b), greater<pair<int, int>>());
    for(auto ele : b)
        cout <<ele.first <<" : " <<ele.second <<"\n";
    return 0;
}
3

That’s a really good idea. But it turns out that it is very tricky to program that in java. Thanks anyway.

BTW the approach that i have come up with (but haven’t tried it and hence don’t know for sure whether it works), is to sort the first array as it is while maintaining a hashtable to preserve the indices. It would be nice to hear from you (or anyone else) regarding how justified you think this approach is in terms of efficiency and easiness of coding.

4

Another way is using a 2d array. You can store the indices in the first column and the values in the second column, so when you sort the array by 2nd column, the first column(which contains indices) gets sorted accordingly.