Как отсортировать и ранжировать вектор в C++ (без использования C++11)

Ваша проблема заключается в неправильном представлении о ранжировании. Индексы массива имеют значение size_t, а не float, поэтому вам нужно будет вернуть vector<size_t>, а не vector<float>.

Тем не менее, ваша сортировка O(n²). Если вы хотите использовать больше памяти, мы можем сократить это время до O(n log(n)):

vector<size_t> rankSort(const float* v_temp, const size_t size) {
    vector<pair<float, size_t> > v_sort(size);

    for (size_t i = 0U; i < size; ++i) {
        v_sort[i] = make_pair(v_temp[i], i);
    }

    sort(v_sort.begin(), v_sort.end());

    pair<double, size_t> rank;
    vector<size_t> result(size);

    for (size_t i = 0U; i < size; ++i) {
        if (v_sort[i].first != rank.first) {
            rank = make_pair(v_sort[i].first, i);
        }
        result[v_sort[i].second] = rank.second;
    }
    return result;
}

Живой пример

ИЗМЕНИТЬ:

Да, это на самом деле становится немного проще, если взять vector<float> вместо float[]:

vector<size_t> rankSort(const vector<float>& v_temp) {
    vector<pair<float, size_t> > v_sort(v_temp.size());

    for (size_t i = 0U; i < v_sort.size(); ++i) {
        v_sort[i] = make_pair(v_temp[i], i);
    }

    sort(v_sort.begin(), v_sort.end());

    pair<double, size_t> rank;
    vector<size_t> result(v_temp.size());

    for (size_t i = 0U; i < v_sort.size(); ++i) {
        if (v_sort[i].first != rank.first) {
            rank = make_pair(v_sort[i].first, i);
        }
        result[v_sort[i].second] = rank.second;
    }
    return result;
}

Живой пример

v_sort[i] - это float (это просто элемент вектора v_sort), а в качестве индексов массива могут использоваться только целочисленные типы.

Вероятно, вы имели в виду v_sort как массив индексов, поэтому вы должны объявить его как std::vector<size_t> или std::vector<int> что-то в этом роде.

UP: Кроме того, учитывая, что вы меняете значения переданного массива, это не элегантный способ передать его по ссылке const.

Подводя итог, следующий код правильно компилируется на моей машине:

std::vector<unsigned> rankSort(float *v_temp, size_t size)
{
    vector <unsigned> v_sort;
    //create a new array with increasing values from 0 to n-1
    for(unsigned i = 0; i < size; i++)
    {
        v_sort.push_back(i);
    }
    bool swapped = false;
    do
    {
        for(unsigned i = 0; i < size; i++)
        {
            if(v_temp[v_sort[i]] > v_temp[v_sort[i+1]]) //error line
            {
                unsigned temp = v_sort[i];
                v_sort[i] = v_sort[i+1];
                v_sort[i+1] = temp;
                swapped = true;
            }
        }
    }
    while(swapped);
    return v_sort;
}

std::vector<unsigned> rankSort(std::vector<float> &v_temp)
{
    return rankSort(&v_temp[0], v_temp.size());
}

Я предлагаю вам принять более надежное решение, воспользовавшись тем, что у вас есть в STL. Для этого мы сначала создадим «индексный вектор», т.е. std::vector<std::size_t> v такое, что для любого i верно v[i] == i:

// I'm sure there's a more elegant solution to generate this vector
// But this will do
std::vector<std::size_t> make_index_vector(std::size_t n) {
    std::vector<std::size_t> result(n, 0);
    for (std::size_t i = 0; i < n; ++i) {
        result[i] = i;
    }
    return result;
}

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

template <typename T, typename A, typename Cmp>
struct idx_compare {
    std::vector<T, A> const& v;
    Cmp& cmp;
    idx_compare(std::vector<T, A> const& vec, Cmp& comp) : v(vec), cmp(comp) {}

    bool operator()(std::size_t i, std::size_t j) {
        return cmp(v[i], v[j]);
    }
};

template <typename T, typename A, typename Cmp>
std::vector<std::size_t> sorted_index_vector(std::vector<T, A> const& vec, Cmp comp) {
    std::vector<std::size_t> index = make_index_vector(vec.size());
    std::sort(index.begin(), index.end(),
        idx_compare<T, A, Cmp>(vec, comp));

    return index;
}

В отсортированном индексном векторе index[0] — это индекс наименьшего значения во входном векторе, index[1] — второе наименьшее значение и так далее. Следовательно, нам нужен еще один шаг, чтобы получить вектор рангов из этого:

std::vector<std::size_t> get_rank_vector(std::vector<std::size_t> const& index) {
    std::vector<std::size_t> rank(index.size());
    for (std::size_t i = 0; i < index.size(); ++i) {
        // We add 1 since you want your rank to start at 1 instead of 0
        // Just remove it if you want 0-based ranks
        rank[index[i]] = i + 1;
    }
    return rank;
}

Теперь соединяем все части вместе:

template <typename T, typename A, typename Cmp>
std::vector<std::size_t> make_rank_vector(
    std::vector<T, A> const& vec, Cmp comp) {
    return get_rank_vector(sorted_index_vector(vec, comp));
}

// I had to stop using default template parameters since early gcc version did not support it (4.3.6)
// So I simply made another overload to handle the basic usage.
template <typename T, typename A>
std::vector<std::size_t> make_rank_vector(
    std::vector<T, A> const& vec) {
    return make_rank_vector(vec, std::less<T>());
}

Результат с [10, 332, 42, 0,9, 0]: [3, 5, 4, 2, 1]. Вы можете найти демонстрацию на gcc 4.3.6, чтобы это поведение.

Вот мои коды, использующие STL для достижения этого в краткой форме, чтобы получить ранг.

template <typename T>
vector<size_t> calRank(const vector<T> & var) {
    vector<size_t> result(var.size(),0);
    //sorted index
    vector<size_t> indx(var.size());
    iota(indx.begin(),indx.end(),0);
    sort(indx.begin(),indx.end(),[&var](int i1, int i2){return var[i1]<var[i2];});
    //return ranking
    for(size_t iter=0;iter<var.size();++iter){
        result[indx[iter]]=iter+1;
    }
    return result;
}