Обратите внимание на другие наши ресурсы:
Youtube | Telegram | VK | Rutube | Dzen | Boosty
¶ Определение
Сортировка подсчетом — это алгоритм, основная идея которого - сортировка последовательности путём подсчёта количества вхождений каждого элемента в ней.
¶ Сферы применения
Сортировка подсчетом используется в тех случаях, когда элементы имеют ограниченный диапазон значений. Алгоритм хорошо подходит для сортировки числовых данных в таких областях, как:
- Статистика, где нужно сортировать данные о частотах или количествах;
- Задачи с фиксированными диапазонами, например, сортировка оценок студентов;
- При сортировке ключей или индексов, где сами данные занимают небольшой диапазон значений.
¶ Принцип работы
Принцип работы упрощённой сортировки подсчётом можно разделить на несколько шагов:
¶ Создание массива счётчиков
Для каждого элемента исходной последовательности создаётся счётчик, который отслеживает количество вхождений этого элемента. Индексы массива счётчиков соответствуют значениям элементов.
¶ Подсчёт элементов
Проходя по каждому элементу исходной последовательности, мы увеличиваем счётчик его количества.
¶ Формирование отсортированной последовательности
После подсчёта всех элементов мы формируем отсортированную последовательность, добавляя элемент в результирующую последовательность столько раз, сколько раз он встречается в исходной последовательности.
¶ Особенности
- Скорость: для данных с небольшим диапазоном значений сортировка подсчетом работает быстрее традиционных алгоритмов, таких как быстрая сортировка или сортировка слиянием.
- Ограничения по диапазону: алгоритм неэффективен для данных с широким диапазоном значений, так как потребуется слишком много памяти для создания массива подсчета.
- Требования к памяти: в худшем случае потребуется память, пропорциональная разности между максимальным и минимальным значениями в исходной последовательности.
- Алгоритм работает только с целыми числами (или данными, которые могут быть эффективно преобразованы в целые).
¶ Вычислительная сложность
Вычислительная сложность алгоритма включает в себя:
- Подсчет вхождений элементов — , где — количество элементов в исходной последовательности.
- Создание и заполнение массива счётчиков — , где — диапазон значений (размер массива счётчиков).
- Формирование отсортированной последовательности — , так как мы проходим по массиву счётчиков и создаём результирующую последовательность.
Таким образом, общая вычислительная сложность — , где — количество элементов, — диапазон значений.
¶ Доказательство
Алгоритм сортировки подсчетом состоит из нескольких этапов, каждый из которых имеет определенную вычислительную сложность:
-
Инициализация массива счётчиков:
- Мы создаём массив счётчиков размером , где — максимальное значение в последовательности. Инициализация этого массива занимает , где .
-
Подсчёт количества каждого элемента:
- Мы проходим по исходной последовательности и увеличиваем соответствующее значение в массиве счётчиков. Это занимает , где — количество элементов в исходной последовательности.
-
Заполнение отсортированной последовательности:
- Мы проходим по массиву счётчиков и для каждого значения записываем его в выходную последовательность столько раз, сколько оно встречается. Это также требует .
Таким образом, итоговая сложность:
где — количество элементов, а — диапазон значений чисел.
¶ Пространственная сложность
Сортировка подсчетом требует дополнительной памяти для массива подсчета и вспомогательного массива для восстановления отсортированных данных:
- Вспомогательный массив — .
- Исходная последовательнсоть — .
Общая пространственная сложность — .
¶ Доказательство
Рассмотрим, сколько памяти занимает алгоритм:
-
Массив счётчиков:
- Массив счётчиков имеет размер , что требует памяти.
-
Выходной массив:
- Мы также создаём выходную последовательность той же длины, что и исходная, что требует памяти.
Таким образом, общая пространственная сложность будет:
где — количество элементов, а — диапазон значений.
¶ Схематическая работа алгоритма
Пусть - исходная последовательность, - массив, в котором мы будем подсчитывать количество вхождений элементов из .
Шаги алгоритма сортировки подсчётами:
¶ Подсчет уникальных элементов
Поcчитать количество каждого уникального элемента во входной последовательности.
Пусть - значение из . Увеличиваем на за каждое встреченное значение .
¶ Заполнение итогового массива
Перебираем все элементы массива , элемент под индексом - это количество значений в исходной последовательности.
¶ Шаг первый
, что означает, что в исходной последовательности отсутствует значение .
¶ Шаг второй
, следовательно в исходной последовательности присутствует значение , поэтому в итоговую последовательность добавляем столько раз, сколько указано в массиве счетчиков (один раз).
¶ Шаг третий
, потому что значение отсутствует в исходной последовательности.
¶ Шаг четвёртый
, так как в исходной последовательности было два элемента с значением . Добавляем их в итоговую последовательность.
¶ Шаг пятый
, добавляем в итоговую последовательность значение .
¶ Шаг шестой
, в исходном массиве была цифра , поэтому в итоговую последовательность добавляем значение один раз.
¶ Итог
В итоге получаем отсортированную последовательность .
¶ Реализация для неотрицательных чисел
Сортировка подсчётом для неотрицательных чисел предполагает, что все элементы последовательности имеют значения больше или равные нулю. Алгоритм подсчитывает количество каждого числа, а затем по этим данным восстанавливает отсортированную последовательность. Этот вариант работает эффективно для последовательности с малым диапазоном значений.
¶ Псевдокод
функция сортировка_подсчетом(последовательность):
если длина(последовательность) < 2:
вернуть последовательность
макс_значение = максимум(последовательность)
счетчик = [0] * (макс_значение + 1)
для каждого элемент в последовательность:
счетчик[элемент] += 1
результат = []
для индекс, количество в перечислить(счетчик):
добавить_в_результат(результат, [индекс] * количество)
вернуть результат
¶ Реализация на Python
Аннотация:
counting_sort - функция сортировки подсчётом
sequence - исходная последовательность
count - массив для подсчёта элементов
maxValue - максимальный элемент из исходной последовательности
num - число исходной последовательность
result - отсортированная исходная последовательность
cnt - число вхождений числа в исходную последовательность
i - элемент исходной последовательности
def counting_sort(sequence):
if len(sequence) < 2:
return sequence
max_value = max(sequence)
count = [0] * (max_value + 1)
for num in sequence:
count[num] += 1
result = []
for i, cnt in enumerate(count):
result.extend([i] * cnt)
return result
¶ Олимпиадная реализация на C++
Аннотация:
typedef - переопределение имени типа данных
countSort - функция сортировки подсчётом
seq - исходная последовательность
c - массив для подсчёта элементов
res - отсортированная последовательность
typedef vector<int> vi;
vi countSort(vi seq) {
vi c(*max_element(seq.begin(), seq.end()) + 1, 0);
for (int i : seq) c[i] += 1;
vi res;
for (int i = 0; i < c.size(); ++i) {
while (c[i] > 0) {
res.push_back(i);
c[i]--;
}
}
return res;
}
¶ Продуктовая реализация на C++
Аннотация:
template - шаблон функции
typename T - шаблонный тип данных параметра
countingSort - функция сортировки подсчётом
sequence - исходная последовательность
maxValue - максимальный элемент из исходной последовательности
count - массив для подсчёта элементов
result - отсортированная последовательность
index - текущий элемент из массива для подсчёта элементов
template <typename T>
vector<T> countingSort(vector<T> sequence) {
if (sequence.size() < 2) return sequence;
T maxValue = *max_element(sequence.begin(), sequence.end());
vector<int> count(maxValue + 1, 0);
for (T data : sequence) count[data] += 1;
vector<T> result;
for (T index = 0; index < count.size(); index++)
while (count[index]-- > 0) result.push_back(index);
return result;
}
¶ Реализация для отрицательных чисел
Сортировка подсчётом для отрицательных чисел требует некоторых дополнительных шагов, поскольку стандартная реализация подсчёта подразумевает использование положительных индексов массива. Для обработки отрицательных чисел необходимо предусмотреть способ корректной работы с отрицательными значениями, учитывая их индексы.
¶ Подход к сортировке отрицательных чисел
Чтобы адаптировать сортировку подсчётом для отрицательных чисел, необходимо выполнить несколько ключевых шагов:
-
Определить минимальное значение: первым делом нужно вычислить минимальное значение в последовательности, чтобы иметь представление о том, насколько нужно сместить индексы массива счётчиков.
-
Сдвиг индексов: поскольку индексы массива для счётчиков должны быть неотрицательными, мы будем смещать все значения массива на такое количество единиц, чтобы минимальное значение соответствовало индексу 0. Это позволит эффективно работать с отрицательными числами.
-
Корректировать индексирование: после сдвига все индексы массива счётчиков будут использоваться относительно минимального значения, корректно сопоставляя исходные отрицательные числа их новым положительным индексам.
¶ Псевдокод
Функция сортировкаПодсчётомСОтрицательными(последовательность):
если длина(последовательность) < 2:
вернуть последовательность
минимум = мин(последовательность)
максимум = макс(последовательность)
счётчики = массив из нулей длиной (максимум - минимум + 1)
результат = массив из нулей длиной (длина(последовательность))
Для каждого элемент в последовательность:
счётчики[элемент - минимум] += 1
Для каждого индекс от 1 до длина(счётчики):
счётчики[индекс] += счётчики[индекс - 1]
Для каждого элемент в обратном порядке последовательность:
счётчики[элемент - минимум] -= 1
результат[счётчики[элемент - минимум]] = элемент
Вернуть результат
¶ Реализация на Python
Аннотация:
counting_sort_negative - функция сортировки подсчётами для отрицательных чисел
sequence - исходная последовательность
min_value - минимальный элемент из исходной последовательности
max_value - максимальный элемент из исходной последовательности
count - массив для подсчёта элементов
result - отсортированная исходная последовательность
i - элемент исходной последовательности
cnt - число вхождений числа в исходную последовательность
def counting_sort_negative(sequence):
if len(sequence) < 2:
return sequence
min_value = min(sequence)
max_value = max(sequence)
count = [0] * (max_value - min_value + 1)
for num in sequence:
count[num - min_value] += 1
result = []
for i, cnt in enumerate(count):
result.extend([i + min_value] * cnt)
return result
¶ Олимпиадная реализация на C++
Аннотация:
typedef - переопределение имени типа данных
countSortNegative - функция сортировки подсчётами для отрицательных чисел
seq - исходная последовательность
l - минимальный элемент из исходной последовательности
h - максимальный элемент из исходной последовательности
res - отсортированная последовательность
c - массив для подсчёта элементов
typedef vector<int> vi;
vi countSortNegative(vi seq) {
int l = *min_element(seq.begin(), seq.end());
int h = *max_element(seq.begin(), seq.end());
vi c(high - low + 1, 0), res(seq.size(), 0);
for (int i : seq)
c[i - l] += 1;
for (int j = 1; j < c.size(); ++j)
c[j] += c[j - 1];
reverse(seq.begin(), seq.end());
for (int i : seq) {
c[i - l] -= 1;
res[c[i - l]] = i;
}
return res;
}
¶ Продуктовая реализация на C++
Аннотация:
template - шаблон функции
typename T - шаблонный тип данных параметра
countingSortForNegative - функция сортировки подсчётами для отрицательных чисел
sequence - исходная последовательность
low - минимальный элемент из исходной последовательности
high - максимальный элемент из исходной последовательности
count - массив для подсчёта элементов
result - отсортированная последовательность
template <typename T>
vector<T> countingSortForNegative(vector<T> sequence) {
if (sequence.size() < 2) return sequence;
int low = *min_element(sequence.begin(), sequence.end());
int high = *max_element(sequence.begin(), sequence.end());
vector<T> result(sequence.size(), 0);
vector<int> count(high - low + 1, 0);
for (T data : sequence)
count[data - low] += 1;
for (int index = 1; index < count.size(); index++)
count[index] += count[index - 1];
reverse(sequence.begin(), sequence.end());
for (T data : sequence) {
count[data - low] -= 1;
result[count[data - low]] = data;
}
return result;
}
¶ Классическая версия
Классическая сортировка подсчётом отличается от упрощённой тем, что она включает этап кумулятивного суммирования. Этот шаг позволяет сохранить устойчивость сортировки, то есть элементы с одинаковыми значениями остаются в том же порядке, что и в исходной последовательности. В классической версии создаётся массив счётчиков, который преобразуется в кумулятивный массив, после чего элементы из исходной последовательности вставляются в правильные позиции в результирующую последовательность. Эта версия эффективна для сортировки, где важен порядок одинаковых элементов.
¶ Реализация для неотрицательных чисел
При реализации сортировки подсчётом для неотрицательных чисел, важно учитывать два аспекта: устойчивость и корректную работу с диапазоном значений.
¶ Устойчивость сортировки
Устойчивость сортировки означает, что элементы с одинаковыми значениями сохраняют свой относительный порядок в отсортированной последовательности. Это важно в тех случаях, когда элементы содержат не только значения для сортировки, но и дополнительные данные, например, индексы или другие признаки.
Чтобы сохранить устойчивость сортировки, в последнем цикле кода (при заполнении итоговой последовательности) итерация по исходной последовательности должна происходить в обратном порядке. Это гарантирует, что если два элемента с одинаковыми значениями встретились в исходной последовательности, то в отсортированной последовательности они окажутся в том же порядке, в котором были в исходной последовательности.
¶ Псевдокод
Функция сортировкаПодсчётом(последовательность):
Если длина(последовательность) < 2:
Вернуть последовательность
счётчики = массив из нулей длиной (макс(последовательность) + 1)
результат = массив из нулей длиной (длина(последовательность))
Для каждого элемент в последовательность:
счётчики[элемент] += 1
Для каждого индекс от 1 до длина(счётчики):
счётчики[индекс] += счётчики[индекс - 1]
Для каждого элемент в обратном порядке последовательности:
счётчики[элемент] -= 1
результат[счётчики[элемент]] = элемент
Вернуть результат
¶ Реализация на Python
Аннотация:
counting_sort - функция сортировки подсчётами
sequence - исходная последовательность
count - массив для подсчёта элементов
result - отсортированная исходная последовательность
def counting_sort(sequence):
if len(sequence) < 2:
return sequence
count = [0] * (max(sequence) + 1)
result = [0] * len(sequence)
for i in sequence:
count[i] += 1
for j in range(1, len(count)):
count[j] += count[j - 1]
for i in reversed(sequence):
count[i] -= 1
result[count[i]] = i
return result
¶ Олимпиадная реализация на C++
Аннотация:
typedef - переопределение имени типа данных
countSort - функция сортировки подсчётами
seq - исходная последовательность
res - отсортированная исходная последовательность
c - массив для подсчёта элементов
typedef vector<int> vi;
vi countSort(vi seq) {
vi res(seq.size(), 0);
vi c(*max_element(seq.begin(), seq.end()) + 1, 0);
for (int i : seq)
c[i] += 1;
for (int j = 1; j < c.size(); j++)
c[j] += c[j - 1];
std::reverse(seq.begin(), seq.end());
for (int i : seq) {
c[i] -= 1;
res[c[i]] = i;
}
return res;
}
¶ Продуктовая реализация на C++
Аннотация:
template - шаблон функции
typename T - шаблонный тип данных параметра
countingSort - функция сортировки подсчётами
sequence - исходная последовательность
count - массив для подсчёта элементов
result - отсортированная исходная последовательность
template <typename T>
std::vector<T> countingSort(std::vector<T> sequence) {
if (sequence.size() < 2) return sequence;
std::vector<T> count(sequence.size(), 0);
std::vector<int> result(*std::max_element(sequence.begin(), sequence.end()) + 1, 0);
for (T data : sequence)
count[data] += 1;
for (int index = 1; index < count.size(); index++)
count[index] += count[index - 1];
std::reverse(sequence.begin(), sequence.end());
for (T data : sequence) {
count[data] -= 1;
result[count[data]] = data;
}
return result;
}