reversible float sort in c/c++

Question

I need to sort some arrays of floats, modify the values, and then construct an array with the original ordering, but the modified values.

In R, I could use the rank() and order() functions to achieve this:
v a vector
v[order(v)] is sorted
v[i] goes in the rank(v)th spot in the sorted vector

Is there some equivalent of these functions in the standard c or c++ libraries? A permutation matrix or other way of encoding the same information would be fine too.
O(n) space and O(nlogn) time would be ideal.

Answer 1

http://www.cplusplus.com/reference/algorithm/sort/

you can stuff your float into a struct that also holds an int, build an array of these structs and store the position of each element in the int field. use the stl sort with a compare function that operates on the float field for your first step, perform your calculations, then sort with a compare function that operates on the int field to get back your original order.

there might be a better way to do this, i'm not really a c++ guy

Answer 2

There is the equivalent to the rank function in C++: it's called nth_element and can be applied on any model of Random Access Container (among which vector and deque are prominent).

Now, the issue seems, to me, that the operate on values might actually modify the values and thus the ranks would change. Therefore I would advise storing the ranks.

1. std::vector<float> to std::vector< std::pair<float, rank_t> >
2. Sort the vector (works without any predicate)
3. Operate on the values
4. std::vector< std::pair<float, rank_t> > to std::vector<float>

Unless of course you want nth_element to be affected by the current modifications of the values that occurred.

Answer 3

The simple answer is to copy the arrays before sorting them, and restore them when you've finished. Only do something more complicated if speed is an issue.

In C++, you could sort an array of indices using a custom comparator to compare the array values, something vaguely like this (not tested, and assuming the floats are in a vector):

class Comparator
{
public:
    explicit Comparator(const std::vector<float>& array) : array(array) {}
    bool operator()(size_t a, size_t b) {return array[a] < array[b];}
private:
    const std::vector<float>& array;
};

void Example(const std::vector<float> &floats)
{
    std::vector<size_t> rank;
    for (int i = 0; i < floats.size(); ++i) rank.push_back(i);
    std::sort(rank.begin(), rank.end(), Comparator(floats));

    std::cout << "First: " << floats[rank.front()] << std::endl;
    std::cout << "Last:  " << floats[rank.back()]  << std::endl;
}

Or, at the cost of extra memory, you could build a vector of (float, rank) pairs, and sort that based on the float values. This approach would also work in C using qsort().

Answer 4

The answer is not to sort the floats, but instead make an array of pointers to the floats, and sort the array of pointers using a comparison function that dereferences the pointers and compares the floats they point to.