Цифровая сортировка
Цифровая cортировка (англ. pigeonhole sort) обладает линейной вычислительной сложностью (О(n)), что является лучшей возможной производительностью для алгоритма сортировки,
так как в любом таком алгоритме каждый сортируемый элемент необходимо
просмотреть хотя бы однажды. Однако, применение алгоритма цифровой
сортировки целесообразно лишь тогда, когда сортируемые предметы имеют
(или их можно отобразить в) диапазон возможных значений, который
достаточно мал по сравнению с сортируемым списком. Эффективность
алгоритма падает всякий раз, когда несколько различных элементов
попадает в одну ячейку. Необходимость сортировки внутри ячеек лишает
алгоритм смысла, так как каждый элемент придётся просматривать более
одного раза. Так что, для простоты и с целью отличить «классическую»
цифровую сортировку от её многочисленных вариантов, укажем, что подсчёт
должен быть обратимым: если два элемента попадают в одну ячейку, то они
должны иметь одинаковое значение. Несколько элементов с одним значением
в одной ячейке не портят картину — их можно просто вставить в
отсортированный список рядом, один за другим (это позволяет применять
цифровую сортировку в качестве устойчивой).
Алгоритм цифровой сортировки действует следующим образом:
- Создаём массив изначально пустых «ячеек», по одной для каждой величины из диапазона ключей.
- Просматриваем изначальный массив, помещая каждый его элемент в свою ячейку.
- Проходим по массиву ячеек в нужном порядке и переносим элементы из непустых ячеек обратно в первоначальный массив.
Эффективность этого алгоритма неявно, но сильно зависит от плотности
элементов в массиве ячеек. Если элементов этого массива намного больше,
чем сортируемых предметов, то шаги 1 и 3 будут относительно медленными.
Сортировку подсчётом применяют редко, потому что её требования редко
удовлетворяются, и часто бывает проще применить другие, более гибкие и
почти такие же быстрые алгоритмы сортировки. В особенности, блочная сортировка является более практичным вариантом сортировки подсчётом. В некотором роде, быстрая сортировка представляет собой обобщённую сортировку подсчётом (всего с двумя ячейками в каждый момент времени).
Литература
|
