обратимая сортировка с плавающей точкой в ​​c / c ++

Question

Мне нужно отсортировать несколько массивов с плавающей точкой, изменить значения, а затем создать массив с исходным порядком, но с измененными значениями.

В R я мог бы использовать функции rank() и order() для достижения этой цели:
v вектор
v[order(v)] сортируется
v[i] идет вrank(v) th место в отсортированном векторе

Есть ли какой-нибудь эквивалент этих функций в стандартных библиотеках c или c ++?Матрица перестановок или другой способ кодирования той же информации тоже подойдут.
O (n) пробел и O (nlogn) время были бы идеальными.

Answer 1

В C ++ есть эквивалент rank функции: она называется nth_element и может применяться к любой модели Контейнер произвольного доступа (среди которых vector и deque являются выдающимися).

Теперь мне кажется, что проблема оперирования значениями может на самом деле изменять значения и, следовательно, ранги будут меняться.Поэтому я бы посоветовал хранить ранги.

1. std::vector<float> до std::vector< std::pair<float, rank_t> >
2. Сортировать vector (работает без предикатов)
3. Работать назначения
4. std::vector< std::pair<float, rank_t> > до std::vector<float>

Если, конечно, вы не хотите, чтобы на nth_element повлияли текущие изменения значений, которые произошли.

Answer 2

Ответ заключается не в сортировке поплавков, а в создании массива указателей на поплавки и сортировке массива указателей с помощью функции сравнения, которая разыменовывает указатели и сравнивает поплавки, на которые они указывают.

Answer 3

Простой ответ - скопировать массивы перед сортировкой и восстановить их, когда вы закончите.Делайте что-то более сложное, только если скорость является проблемой.

В C ++ вы можете отсортировать массив индексов, используя собственный компаратор для сравнения значений массива, что-то вроде этого (не проверено, и предполагается, что числа с плавающей точкойв векторе):

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;
}

Или, за счет дополнительной памяти, вы можете построить вектор из пар (float, rank) и отсортировать его по значениям float.Этот подход также будет работать в C с использованием qsort().

Answer 4

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

вы можете поместить ваш float в структуру, которая также содержит int, построить массив этих структур и сохранить положение каждого элемента в поле int. Для первого шага используйте сортировку stl с функцией сравнения, которая работает с полем с плавающей запятой, выполните вычисления, а затем выполните сортировку с помощью функции сравнения, которая работает с полем int, чтобы вернуть исходный порядок.

может быть, есть лучший способ сделать это, я на самом деле не парень с ++