Есть два случая, в которых вы можете захотеть использовать сортировку подсчетом. Во-первых, у вас может быть массив реальных чисел, которые вы хотите отсортировать, и цель состоит в том, чтобы отсортировать эти числа. Во-вторых, у вас может быть массив значений для сортировки, каждое из которых отсортировано в соответствии с некоторым ключом, представляющим собой число в фиксированном диапазоне.
В первом случае, когда вы просто сортируете числа, нет причин, по которым вам нужно преобразовывать гистограмму в кумулятивную гистограмму. Поскольку числа — это просто числа, вы можете сортировать массив, не переставляя исходные значения в порядке сортировки, а просто создавая новый список чисел на основе частотной гистограммы. Например, вот как вы можете это сделать:
/* 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[ i])] - 1 элемент меньше или равен ему. Предполагая, что в массиве нет повторяющихся значений, итерация по массиву A и изменение положения всего в соответствии с этой формулой правильно расположит массив в отсортированном порядке.
Все немного сложнее, если у нас есть дубликаты. Предположим, что есть два элемента A[i] и A[j], где key(A[i]) = key(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;
}
Цикл немного странный из-за обратного отсчета с беззнаковыми значениями. В этом вопросе подробно описано, как правильно с этим справиться.
person
templatetypedef
schedule
26.08.2015
