Сортировка массива с небольшими числами, имея вторичный массив с начальными индексами
У меня есть небольшой массив из 7 элементов, которые могут иметь значения от 0 до примерно 6 (очень маленькие числа). С такой конфигурацией сортировка по подсчету действительно очень эффективна, но у меня есть другой массив для отслеживания индексов первого массива. Например:
основной массив: (начальный) {0,3,5,1,0,2,4} вторичный массив (начальный) {0,1,2,3,4,5,6}
основной массив: (отсортировано) {5,4,3,2,1,0,0}
вторичный массив (отсортированный) {2,6,1,5,3,4,0}
Первый массив должен быть отсортирован обычным способом, а индексы второго массива в конечном итоге должны соответствовать соответствующим элементам в первом массиве.
Как сортировать массивы по этим правилам, используя сортировку подсчетом, а не пузырьковую сортировку?
У меня есть рабочая реализация с использованием пузырьковой сортировки, но я ожидаю, что сортировка по подсчету будет работать быстрее со следующим набором.
Действительно ли «быстрее» вызывает беспокойство, когда вы имеете дело с такими маленькими массивами? Это просто игрушка или реальное приложение, которое имеет значение?
Разница между пузырьковой сортировкой (которая равна O(n^2)) и сортировкой по подсчету (которая равна O(n) при условии, что количество потенциальных значений является константой) актуальна только в том случае, если у вас очень большие массивы. В любом случае, если вас беспокоит производительность вашего реального приложения, вам следует профилировать ее и сравнить результаты различных решений.
ОТ: «вторичный массив (отсортированный) {2,6,1,5,3,4,0}» -> «вторичный массив (отсортированный) {2,6,1,5,3,0,4}», я думаю
Отвечает ли это на ваш вопрос? Как я могу отсортировать два вектора одинаково, используя критерии, которые используют только один из векторов?
Предположим, у вас есть что-то вроде std::sort, где вы можете отсортировать только один вектор, единственный способ, который я вижу сразу, - это отсортировать только второй массив, а затем построить новый «первый» массив с информацией, взятой из него (что является еще одним O (n) бежать, но в этом случае его нельзя избежать). Если вам нужна сортировка на месте и для первого массива, реализуйте сортировку самостоятельно, чтобы вы могли сравнивать значения в одном массиве, но менять их местами в обоих.
Ответы 1
Во-первых, это кажется намного лучше, поскольку в комментариях предлагается просто использовать структуру, содержащую как элементы, так и их индексы: struct item {целое значение; внутренний индекс; }. Затем вы сортируете их, используя любой вид, который вам нравится, используя только item.value, и у вас есть индексы, которые затем сортируются за вас.
Однако, если вы специально хотите использовать сортировку по подсчету для заданных структур данных, я бы, вероятно, изменил этот алгоритм сортировки по подсчету с простого подсчета на сохранение индексов. Например, там, где вы обычно храните счетчики std::vector или std::map<int, int> чтобы сохранить количество каждого значения в массиве, вместо этого вы можете использовать вектор/карту векторов/наборов. Здесь элемент с индексом 0 будет хранить все индексы исходного массива, где значение равно 0. Пример использования только векторов:
скажем, original_array содержит {0,3,5,1,0,2,4}
ваша новая структура:
std::vector<std::vector<int>> counters(7); // one vector for each possible value from 0 to 6
подсчет:
for (int index = 0; index < original_array.size(); ++index)
{
const int& value_at_index = original_array[index];
counters[value_at_index].push_back(index);
}
в конце концов ваши счетчики будут содержать всю необходимую вам информацию. Для каждого элемента массива счетчиков количество подэлементов соответствует его частоте, а сами подэлементы дают индексы исходных элементов. Также обратите внимание на то свойство, что это стабильная сортировка, т. е. элементы равного значения сохраняют порядок своих индексов. Пример того, что находится внутри индексов после этого:
0:0,4
1:3
2:5
3:1
4:6
5:2
6:-
Надеюсь это поможет!
создайте массив с парами
{element, original index}и отсортируйте его по элементу.