Сортировка распределением, также известная как сортировка подсчётом, является эффективным методом сортировки, который работает с массивами, где значения находятся в известном диапазоне. Этот метод особенно полезен, когда диапазон значений невелик, так как он использует дополнительную память для подсчёта количества каждого элемента. В отличие от других алгоритмов, сортировка распределением не требует сравнения элементов, что делает её быстрой и простой в реализации. В этой презентации мы рассмотрим принцип работы метода, его алгоритм и пример кода на языке C++.
Принцип работы метода
Метод использует дополнительный массив для подсчёта количества каждого элемента
Сначала определяется минимальное и максимальное значение в массиве
Затем создаётся массив подсчёта размером (max - min + 1)
Каждый элемент исходного массива увеличивает соответствующий счётчик
На основе счётчиков массив заполняется отсортированными значениями
Алгоритм сортировки распределением
Входные данные: массив A из n элементов, диапазон [minVal, maxVal]
Инициализировать массив C размером (maxVal - minVal + 1) нулями
Для каждого элемента x в A: увеличить C[x - minVal] на 1
Инициализировать индекс i = 0 для массива A
Для каждого значения v от minVal до maxVal: пока C[v - minVal] > 0, установить A[i] = v и увеличить i
Массив A теперь отсортирован
Пример кода на C++
Включение необходимых библиотек: и
Функция distSort принимает вектор, минимальное и максимальное значение
Создаётся массив count для подсчёта элементов
Цикл проходит по всем элементам и увеличивает соответствующие счётчики
Второй цикл заполняет исходный массив отсортированными значениями
В функции main создаётся массив, определяются min и max, вызывается distSort
Сортировка распределением является простым и эффективным методом, особенно когда диапазон значений известен заранее. Этот метод не требует сложных сравнений и операций, что делает его быстрым и лёгким в реализации. Однако он требует дополнительной памяти, что может быть недостатком при работе с большими массивами. В целом, сортировка распределением — это мощный инструмент для сортировки данных в ограниченных диапазонах, который находит применение в различных областях программирования и анализа данных.
