C vector sorting and mapping from unsorted to sorted elements-CodePudding

I have to perform the following task. Take a std::vector<float>, sort the elements in descending order and have an indexing that maps the unsorted elements to the sorted ones. Please note that the order really matters: I need a map that, given the i-th element in the unsorted vector, tells me where this element is found in the sorted one. The vice-versa has been achieved already in a pretty smart way (through c lambdas) e.g., here: C sorting and keeping track of indexes. Nevertheless, I was not able to find an equally smart way to perform the "inverse" task. I would like to find a fast way, since this kind of mapping has to be performed many times and the vector has big size.
Please find in the following a simple example of what I need to achieve and my (probably suboptimal, since it relies on std::find) solution of the problem. Is it the most fast/efficient way to perform this task? If not, are there better solutions?

Example

Starting vector: v = {4.5, 1.2, 3.4, 2.3}

Sorted vector: v_s = {4.5, 3.4, 2.3, 1.2}

What I do want: map = {0, 3, 1, 2}

What I do not want: map = {0, 2, 3, 1}

My solution

template <typename A> std::vector<size_t> get_indices(std::vector<A> & v_unsorted, std::vector<A> & v_sorted) {
  std::vector<size_t> idx;
  for (auto const & element : v_unsorted) {
    typename std::vector<A>::iterator itr = std::find(v_sorted.begin(), v_sorted.end(), element);
      idx.push_back(std::distance(v_sorted.begin(), itr));
  }
  return idx;
}

Thanks a lot for your time, cheers!

CodePudding user response：

Once you have the mapping from sorted to unsorted indices, you only need a loop to invert it.

I am building on the code from this answer: https://stackoverflow.com/a/12399290/4117728. It provides a function to get the vector you do not want:

#include <iostream>
#include <vector>
#include <numeric>      // std::iota
#include <algorithm>    // std::sort, std::stable_sort

using namespace std;

template <typename T>
vector<size_t> sort_indexes(const vector<T> &v) {

  // initialize original index locations
  vector<size_t> idx(v.size());
  iota(idx.begin(), idx.end(), 0);

  // sort indexes based on comparing values in v
  // using std::stable_sort instead of std::sort
  // to avoid unnecessary index re-orderings
  // when v contains elements of equal values 
  stable_sort(idx.begin(), idx.end(),
       [&v](size_t i1, size_t i2) {return v[i1] < v[i2];});

  return idx;
}

Sorting the vector is O(N logN) your code calls find N times resulting in O(N*N). On the other hand, adding a single loop is only linear, hence sorting plus the loop is still O(N log N).

int main() {
    std::vector<double> unsorted{4.5, 1.2, 3.4, 2.3};
    auto idx = sort_indexes(unsorted);
    for (auto i : idx) std::cout << unsorted[i] << "\n";
    
    // the vector you do not want
    for (auto i : idx) std::cout << i << "\n";
    
    // invert it
    std::vector<size_t> idx_inverse(idx.size());
    for (size_t i=0;i<idx.size();  i) idx_inverse[ idx[i] ] = i;
    
    // the vector you do want
    for (auto i : idx_inverse) std::cout << i << "\n";
}

Live Demo

CodePudding user response：

You can use the code below.

My version of get_indices does the following:

Create a vector of indices mapping sorted -> unsorted, using code similar to the one in the link you mentioned in your post (C sorting and keeping track of indexes).
Then by traversing those indices once, create the sorted vector, and the final indices mapping unsorted -> sorted.

The complexity is O(n * log(n)), since the sort is done in O(n * log(n)), and the final traversal is linear.

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

template <typename T>
std::vector<size_t> get_indices(std::vector<T> const & v_unsorted, std::vector<T> & v_sorted) 
{
    std::vector<size_t> idx_sorted2unsorted(v_unsorted.size()); 
    std::iota(idx_sorted2unsorted.begin(), idx_sorted2unsorted.end(), 0);

    // Create indices mapping (sorted -> unsorted) sorting in descending order:
    std::stable_sort(idx_sorted2unsorted.begin(), idx_sorted2unsorted.end(),
        [&v_unsorted](size_t i1, size_t i2) 
            { return v_unsorted[i1] > v_unsorted[i2]; }); // You can use '<' for ascending order

    // Create final indices (unsorted -> sorted) and sorted array:
    std::vector<size_t> idx_unsorted2sorted(v_unsorted.size());
    v_sorted.resize(v_unsorted.size());
    for (size_t i = 0; i < v_unsorted.size();   i)
    {
        idx_unsorted2sorted[idx_sorted2unsorted[i]] = i;
        v_sorted[i] = v_unsorted[idx_sorted2unsorted[i]];
    }
    return idx_unsorted2sorted;
}

int main() 
{
    std::vector<double> v_unsorted{ 4.5, 1.2, 3.4, 2.3 };
    std::vector<double> v_sorted;
    std::vector<size_t> idx_unsorted2sorted = get_indices(v_unsorted, v_sorted);
    for (auto const & i : idx_unsorted2sorted)
    {
        std::cout << i << ", ";
    }
    return 0;
}

Output:

0, 3, 1, 2,