Берестнев Даниил 19.12

1.

АЛГОРИТМЫ
СОРТИРОВКИ.
СОРТИРОВКА
ПОДСЧЕТОМ
Берестнев Даниил
Группа УНБО-05-24
Декабрь 2024

2.

Методы сортировки
Сортировка - один из наиболее распространенных процессов
современной обработки информации. Это распределение
элементов множества по группам в соответствии с
определенными правилами.
(Е.В.Андреева)
ПРОСТЫЕ
СЛОЖНЫЕ
Подсчетом
Вставками
Выбором
Обменом
Метод Шелла
С разделениями
Слияниями
Пирамидальная

3.

Как работает сортировка подсчетом?
Сортировка с подсчетом - это линейный алгоритм сортировки, который
применим, когда мы имеем дело с небольшим диапазоном целых чисел
или других ограниченных значений. Этот алгоритм основан на подсчете
количества вхождений каждого элемента в массив и его последующей
упорядочивании.
Например:
У нас есть массив чисел, и мы знаем, что все эти числа находятся в
диапазоне от 0 до 9. Мы можем создать "счетчик" (Counting Array) длиной
10 (по количеству возможных значений), и для каждого элемента в
исходном массиве увеличивать соответствующий счетчик в Counting Array.
Таким образом, мы получим информацию о том, сколько раз каждое число
встречается в исходном массиве.
Затем мы можем воспользоваться этой информацией, чтобы построить
отсортированный массив. Мы начнем с наименьшего числа (0) и будем
добавлять его в новый массив столько раз, сколько раз оно встречается в
исходном массиве. После этого перейдем к следующему числу и так
далее.

4.

Пример

5.

Пример на Python
Давайте посмотрим на простую
реализацию сортировки с подсчетом
на Python

6.

Когда использовать сортировку с
подсчетом?
Сортировка с подсчетом - отличный выбор, когда:
У вас есть ограниченный диапазон значений.
Вам необходимо сортировать большие объемы данных, и
при этом ограниченное количество уникальных значений.
Вам важна стабильность сортировки, то есть сохранение
относительного порядка равных элементов.
Однако следует помнить, что этот алгоритм неэффективен
при большом разбросе значений и когда диапазон значений
слишком велик.