How to sort an array(in ascending order) based on the ranks of each element which is in the another array?

Question

Let two arrays

arr = [1,5,6,3,10] 


rank = [100,0,1,100,2]

Based on the rank array (Which holds the ranks of the mirror elements in the arr) the result should be

[5,6,10,1,3]

The first element in the result is 5

(The index of 5 in arr is arr[1] and the index of 0 in rank is rank[1]. This is how we have to take ranks. 0 is smallest of all ranks so 5 is printed first )

The second element in the result is 6

The index of 6 in arr array is at the index arr[2] and its rank is 1 because that is at the index rank[2]. 1 is the second smallest of all ranks so 6 is printed next) This is how we have to sort the array based on the rank array.

Here if two ranks are same then we have to compare the values in the array itself and print the smaller first
arr[0] = 1 and arr[3] = 3 Both having same ranks 100. So compare those elements and print the smallest value. That gives the

result 5,6,10,1,3

Answer 1

The short answer is: std::sort.

The long answer depends on how you store the values and the ranks, whether you can afford to copy them, and whether you also need the ranks sorted. For the following I assumed that you do not need the ranks sorted and the sorting is done on the original container of values. It is not the most efficient implementation, but it is simple enough to get you started:

#include <vector>
#include <utility>
#include <algorithm>
#include <iostream>
#include <iterator>

template <typename Iter,typename RankIter>
void rank_sort(Iter begin,Iter end,RankIter rankbegin){
    std::vector<std::pair<typename std::iterator_traits<RankIter>::value_type,
                          typename std::iterator_traits<Iter>::value_type >> res;
    for (auto beg = begin; beg != end; ++beg,++rankbegin) res.emplace_back(*rankbegin,*beg); 
    std::sort(res.begin(),res.end());
    for (const auto& e : res){
        *begin = e.second;
        ++begin;
    }
}


int main() {
    std::vector<int> arr{1,5,6,3,10};
    std::vector<int> rank{100,0,1,100,2};
    rank_sort(arr.begin(),arr.end(),rank.begin());
    for (const auto& a : arr) { std::cout << a << " ";}
}

The basic idea is to create a std::vector<std::pair<int,int>> and then simply sort that via std::sort. The rest of the code is about copying the values and ranks into that vector and copying the values out of it after sorting.

If possible you should store the values and ranks in a std::vector<std::pair<int,int>> in the first place. Then sorting them is trivial. Alternatively, as mentioned in a comment, you can use a sorted container, like eg a std::map.