Ковшовая сортировка
Bucket sort или bin sort — это алгоритм сортировки, который работает путем распределения элементов массива по нескольким сегментам . Затем каждое ведро сортируется индивидуально либо с использованием другого алгоритма сортировки, либо путем рекурсивного применения алгоритма сортировки ведра. Это сортировка по распределению , обобщение сортировки по ячейкам , которая позволяет использовать несколько ключей в корзине, и является двоюродным братом сортировки по основанию в варианте от большего к меньшему значащему разряду. Сегментная сортировка может быть реализована с помощью сравнений и, следовательно, также может считаться алгоритмом сортировки по сравнению . Вычислительная сложностьзависит от алгоритма, используемого для сортировки каждого сегмента, количества используемых сегментов и равномерности распределения входных данных.
Пусть array обозначает массив для сортировки, а k обозначает количество используемых сегментов. Можно вычислить максимальное линейное время значения ключа , перебирая все ключи один раз. Функция floor должна использоваться для преобразования числа с плавающей запятой в целое число (и, возможно, приведения типов данных). Функция nextSort — это функция сортировки, используемая для сортировки каждого сегмента. Обычно используется сортировка вставками , но могут использоваться и другие алгоритмы, такие как сортировка выбором или сортировка слиянием . Использование самого BucketSort в качестве nextSort создает относительную сортировку по основанию.; в частности, случай n = 2 соответствует быстрой сортировке (хотя потенциально с плохим выбором опорной точки).
Когда входные данные содержат несколько ключей, близких друг к другу (кластеризация), эти элементы, скорее всего, будут помещены в одно и то же ведро, что приводит к тому, что некоторые ведра содержат больше элементов, чем в среднем. Наихудший сценарий возникает, когда все элементы помещаются в одно ведро. Тогда общая производительность будет определяться алгоритмом, используемым для сортировки каждого сегмента, например алгоритмы сортировки вставками или алгоритмы сортировки сравнением , такие как сортировка слиянием .
