Подсчет сортировки: зачем нужна сумма предыдущих подсчетов?
Я читал о подсчете сортировки и один из шагов алгоритма
for(i = 1 to k)
c[i] = c[i]+c[i-1];
Зачем нам этот шаг?
Почему мы не можем использовать это вместо
for(i = 0 to k)
while(c[i]--)
Output i/Use i as key.
Одна проблема, о которой я подумал, заключалась в том, что нам нужны сами данные (вероятно, как строка, которая ссылается на определенный индекс).
Но тогда мы могли бы использовать 2d вектор.
Что плохо в этом подходе, где мы сортируем данные от 0 до 99.
int a[100];
for(int i = 0 ; i < 100; ++i)
a[i] = 0;
string s;
vector<vector<string>> data(100);
int temp;
for(int i = 0 ; i < n ; ++i){
cin>>temp;
a[temp]++;
getline(cin,s);
data[temp].push_back(s);
}
for(int i = 0 ; i < 100; ++i){
int current = 0;
while(a[i]--){
cout<<data[i][current]<<" ";
++current;
}
}
Решение
РЕДАКТИРОВАТЬ: Я значительно пересмотрел этот ответ на основе комментариев.
Есть два случая, в которых вы можете использовать сортировку подсчета. Во-первых, у вас может быть массив фактических чисел, которые вы хотите отсортировать, и цель состоит в том, чтобы отсортировать эти числа. Во-вторых, у вас может быть массив значений для сортировки, каждое из которых отсортировано по некоторому ключу, который является числом в фиксированном диапазоне.
В первом случае — когда вы просто сортируете числа — нет причин, по которым вам нужно преобразовывать гистограмму в накопительную гистограмму. Поскольку числа — это просто числа, вы можете отсортировать массив не путем перестановки начальных значений в отсортированном порядке, а просто путем генерации нового списка чисел на основе частотной гистограммы. Например, вот как вы можете это сделать:
/* Initialize histogram. */
const unsigned kMaxValue = 100;
std::vector<unsigned> counts(kMaxValue);
/* Read values. */
const unsigned kNumValues = 100;
for (unsigned i = 0; i < kNumValues; i++) {
unsigned nextValue;
std::cin >> nextValue; // Don't forget error-checking!
counts[nextValue]++;
}
/* Output values. */
std::vector<unsigned> result;
result.reserve(kNumValues);
for (unsigned i = 0; i < counts.size(); i++) {
for (unsigned j = 0; j < counts[i]; j++) {
result.push_back(i);
}
}
Обратите внимание, что числа, которые добавляются к result вектор не считывается из входных данных, а генерируется просто с помощью счетчика цикла.
Во втором случае, когда у вас есть элементы для сортировки, а у каждого элемента есть ключ, невозможно использовать описанный выше подход, потому что вы не можете восстановить элементы просто путем подсчета. Вместо этого вам нужно будет сделать что-то более умное, что на самом деле включает в себя перестановку элементов из входной последовательности.
Вот тут-то и возникает идея частотной гистограммы. Основная идея заключается в следующем: мы хотим определить для каждого элемента входного массива индекс, по которому этот элемент должен оказаться в отсортированном массиве. Давайте представим, что мы начнем с получения частотной гистограммы H для входного массива. Эта гистограмма обладает тем свойством, что H [i] сообщает нам, сколько существует различных элементов с ключом i. Теперь предположим, что мы создаем кумулятивную частотную гистограмму C, где C [i] = C [0] + C [1] + … + C [i]. В этом случае C [i] сообщает нам, сколько элементов во входном массиве имеют ключ меньше или равный ему.
Представьте, что у вас есть только входной массив и гистограмма кумулятивной частоты. Что вы могли бы сделать с этим? Хорошо, предположим, что у вас есть элемент A [i] из исходного массива. Основываясь на кумулятивной частотной гистограмме, мы знаем, что в массиве есть элементы C [i], ключ которых меньше или равен A [i]. Поэтому, если мы хотим переупорядочить входной массив так, чтобы все было в порядке сортировки, мы могли бы поместить элемент A [i] в позицию C [key (A [i])] — 1, так как есть C [key (A [] я])] — 1 элементов меньше или равно ему. Предполагая, что в массиве нет повторяющихся значений, итерация по массиву A и перестановка всего в соответствии с этой формулой позволят правильно расположить массив в отсортированном порядке.
Все немного сложнее, если у нас есть дубликаты. Предположим, есть два элемента A [i] и A [j], где ключ (A [i]) = ключ (A [j]). В этом случае мы не можем поместить оба элемента в положение C [key (A [i])] — 1, так как они будут сталкиваться. Однако мы могли бы сделать следующее. Мы поместим один из элементов в положение C [key (A [i])] — 1, затем деструктивно изменим массив C, вычтя 1 из C [key (A [i])]. Затем, когда мы увидим элемент A [j], мы поместим его в позицию C [key (A [j])] — 1, которая является пустой ячейкой. Интуитивно понятно, что вся идея наличия кумулятивной частотной гистограммы заключается в том, чтобы иметь возможность мгновенно знать, где позиционировать объекты, сохраняя количество объектов, которые появятся перед любым конкретным элементом с данным ключом. Каждый раз, когда мы видим элемент с некоторым ключом, мы хотим указать, что для любого будущего элемента с тем же ключом, перед ним будет на один элемент меньше.
Так зачем сканировать в обратном направлении? С таким же успехом мы могли бы выполнить сканирование вперед, но преимущество сканирования назад заключается в том, что он сортирует элементы стабильно. То есть, если у вас есть несколько элементов с одним и тем же ключом, все они будут отображаться в том же относительном порядке в выходной последовательности, как и во входной последовательности.
Вот некоторый код, демонстрирующий, как вы можете использовать это:
/* Initialize histogram. */
const unsigned kMaxValue = 100;
std::vector<unsigned> counts(kMaxValue);
/* Read values. Each value will be a string with an associated key. */
const unsigned kNumValues = 100;
std::vector<std::pair<unsigned, std::string>> elems;
elems.reserve(kNumValues);
for (unsigned i = 0; i < kNumValues; i++) {
unsigned key;
std::cin >> key; // Don't forget error-checking!
std::string value;
std::cin >> value; // Don't forget error-checking!
elems.push_back(std::make_pair<key, value>);
counts[key]++;
}
/* Transform histogram into cumulative histogram. */
for (unsigned i = 1; i < counts.size(); i++) {
counts[i] += counts[i - 1];
}
/* Output values. */
std::vector<unsigned> result(kNumValues);
for (unsigned i = counts.size() - 1; i >= 0 && i < counts.size(); i--) { // See note
result[--counts[elems[i].first]] = elems[i].second;
}
Цикл немного странный из-за обратного отсчета со значениями без знака. Этот вопрос подробно, как правильно с этим справиться.
Другие решения