Сортировка вектора (двойной точности) вещественных чисел и получение их - PullRequest
Новая
       30

Сортировка вектора (двойной точности) вещественных чисел и получение их

6 голосов
/ 24 декабря 2010

В C ++ хотелось бы отсортировать длинный (2^20) вектор реалов, очевидно, sort() делает свое дело.Я использовал R раньше, чем я привык к хорошей функции order(), которая дает перестановку, которая приводит к отсортированному вектору.

Пример: 

x = {24, 55, 22, 1}

Тогда перестановка 

perm = {3, 2, 0, 1}

Отображает исходный x на отсортированный x в порядке возрастания.

Возможно, я могу реализовать некоторую пузырьковую сортировку, которая не только сортирует x, но и выполняет те же транспонирования для вектора {0,1,2,...}и выводит оба, но я считаю, что кто-то, должно быть, думал об этом и особенно сделал это эффективно.

Ответы [ 3 ]

5 голосов
/ 24 декабря 2010

Я бы сказал, что лучшим способом было бы создать вектор с целыми числами 0..N, а затем отсортировать этот массив с помощью функции сравнения, которая сравнивает соответствующие элементы вектора, для которого вы пытаетесь найти отсортированную перестановку.Что-то вроде: 

#include <vector>
#include <algorithm>

template<class T> class sorter {
    const std::vector<T> &values;
public:
    sorter(const std::vector<T> &v) : values(v) {}
    bool operator()(int a, int b) { return values[a] < values[b]; }
};

template<class T> std::vector<int> order(const std::vector<T> &values)
{
    std::vector<int> rv(values.size());
    int idx = 0;
    for (std::vector<int>::iterator i = rv.begin(); i != rv.end(); i++)
        *i = idx++;
    std::sort(rv.begin(), rv.end(), sorter<T>(values));
    return rv;
}

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

4 голосов
/ 24 декабря 2010

Вы можете использовать std::sort для сортировки списка пар {(24, 0), (55, 2), (22, 0), (1, 1)}. Это не особенно красиво, но я обычно делаю что-то вроде этого: 

#include <vector>
#include <algorithm>
#include <utility>

typedef std::pair<double, int> Pair;

struct CmpPair
{
    bool operator()(const Pair& a, const Pair& b)
    { return a.first < b.first; }
};

void sortingPermutation(
    const std::vector<double>& values,
    std::vector<int>& permutation)
{
    std::vector<Pair> pairs;
    for (int i = 0; i < (int)values.size(); i++)
        pairs.push_back(Pair(values[i], i));

    std::sort(pairs.begin(), pairs.end(), CmpPair());

    typedef std::vector<Pair>::const_iterator I;
    for (I p = pairs.begin(); p != pairs.end(); ++p)
        permutation.push_back(p->second);
}

Вот тест: 

#include <iostream>

int main()
{
    std::vector<double> values;
    values.push_back(24);
    values.push_back(55);
    values.push_back(22);
    values.push_back(1);

    std::vector<int> permutation;
    sortingPermutation(values, permutation);

    typedef std::vector<int>::const_iterator I;
    for (I p = permutation.begin(); p != permutation.end(); ++p)
        std::cout << *p << " ";
    std::cout << "\n";
}
3 голосов
/ 24 декабря 2010

Редактировать

Лучше, чем раньше подход без использования вспомогательных векторов: ( источник на идеоне ): 

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

template<class Vals>
void sortingPermutation(const Vals& values, std::vector<int>& v){
  int size = values.size(); 
  v.clear(); v.reserve(size);
  for(int i=0; i < size; ++i)
    v.push_back(i);

  std::sort(v.begin(), v.end(), [&values](int a, int b) -> bool { 
    return values[a] < values[b];
  });
}

int main()
{
    std::vector<double> values;
    values.push_back(24);
    values.push_back(55);
    values.push_back(22);
    values.push_back(1);

    std::vector<int> permutation;
    sortingPermutation(values, permutation);

    typedef std::vector<int>::const_iterator I;
    for (I p = permutation.begin(); p != permutation.end(); ++p)
        std::cout << *p << " ";
    std::cout << "\n";
}

Я использую лямбдуиз C ++ 0x, но его можно заменить на простой объект-функтор: 

template<class T>
struct CmpPairs{
  CmpPairs(const std::vector<T> &v): v_(v) {}
  std::vector<T> v_;
  bool operator()(int a, int b){ return v_[a] < v_[b]; }
};

template<class T>
CmpPairs<T> CreateCmpPairs(const std::vector<T> & v) { return CmpPairs<T>(v); }
//in sortingPermutation:
std::sort(v.begin(), v.end(), CreateCmpPairs(values));

Источник старого решения с std::map: ideone

...