Блог

Главная - Вопросы по программированию - сортировка компаратора c с использованием вспомогательного массива

сортировка компаратора c с использованием вспомогательного массива

#c #sorting #lambda #stl

#c #сортировка #лямбда #stl

Вопрос:

У меня есть массив (скажем values ), который нельзя изменить. Я хочу знать, отсортированы ли значения в этом массиве, какова будет их конечная позиция / индекс. Итак, для этого я просто использую код, как показано ниже:

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

int main() {
    std::vector<unsigned> position(11, 0);
    std::iota(position.begin(), position.end(), 0);
    std::vector<unsigned> values = {140, 141, 118, 119, 122, 123, 128, 129, 133, 134, 138, 139};
    
    auto value_comparator = [amp;values](const unsignedamp; index1, const unsignedamp; index2) {
        return (values[index1] < values[index2]);
    };
    
    std::sort(position.begin(), position.end(), value_comparator);
    
    for (auto val : position) {
        std::cout << val << " ";
    }
    std::cout << std::endl;

    return 0;
}

Фактический результат:

 2 3 4 5 6 7 8 9 10 0 1

Ожидаемый результат:

 10 11 0 1 2 3 4 5 6 7 8 9

Я пытаюсь понять, почему результат такой, как показано выше. Похоже, что используется STL IntroSort . Ищу какой-то ввод, прежде чем копать глубже.

Спасибо.

Комментарии:

1. Для меня это очень похоже на правильный вывод, почему вы ожидаете, например, что первые индексы будут 10 и 11 , где соответствующие значения 138 и 139 , которые не являются самыми низкими values ?!

2. @lubgr 10 и 11 показывает, что 140 отсортированная позиция 10 и 141 отсортированная позиция 11 .

3. @RachitAgrawal Это не то, что делает ваш код. Ваш код сортирует второй массив по отношению к значениям в первом. Таким 2 образом, индекс 0 показывает, что значение в позиции 2 в вашем втором массиве является первым элементом при его сортировке.

4. Что означает @super, так это то, что ваш вывод показывает исходный индекс значений.

5. Спасибо всем. Не осознавал этого.

Ответ №1:

Ваш код сортирует индексы по их значению в массиве. Таким образом, результат будет иметь в первой позиции индекс наименьшего значения, во второй — индекс второго наименьшего и так далее.

Чтобы получить то, что вы хотите от этого, вы можете, например, выполнить следующее:

 std::vector<unsigned> result(position.size());
for(unsigned i = 0; i < position.size();   i) {
    result[position[i]] = i;
}