Ковшовая сортировка

Ковшовая сортировка

Учебный класс	Алгоритм сортировки
Структура данных	Множество
Пессимистический производительность	${\ Displaystyle О \ влево (п ^ {2} \ вправо)}$
Средняя производительность	${\ Displaystyle О \ влево (п + {\ гидроразрыва {п ^ {2}} {к}} + к \ вправо)}$, где k - количество ведер. .${\ Displaystyle О (п), {\ текст {когда}} к \ приблизительно п}$
Сложность пространства в наихудшем случае	${\ Displaystyle О (п \ CDOT K)}$

Эта статья требует внимания специалиста по информатике . Добавьте причину или параметр обсуждения в этот шаблон, чтобы объяснить проблему со статьей. WikiProject Computer science может помочь нанять эксперта. ( Ноябрь 2008 г. )

Элементы распределяются по бункерам

Затем элементы сортируются в каждой ячейке.

Сортировка по корзине , или сортировка по ячейкам , - это алгоритм сортировки, который работает путем распределения элементов массива по ряду сегментов . Затем каждое ведро сортируется индивидуально, либо с использованием другого алгоритма сортировки, либо путем рекурсивного применения алгоритма сортировки. Это разновидность распределения , обобщение сортировки по ячейкам , и она является родственником сортировки по основанию счисления в виде наиболее значимых и наименее значимых цифр. Сортировка по сегментам может быть реализована со сравнениями и, следовательно, также может рассматриваться как алгоритм сортировки сравнения . Вычислительная сложность зависит от алгоритма, используемого для сортировки каждой корзины, количества используемых корзин и от того, равномерно ли распределены входные данные.

Сортировка ведра работает следующим образом:

1. Создайте массив из изначально пустых «ведер».
2. Scatter : перейдите по исходному массиву, поместив каждый объект в свое ведро.
3. Отсортируйте каждое непустое ведро.
4. Собрать : посетить сегменты по порядку и вернуть все элементы в исходный массив.

Псевдокод [ править ]

функция bucketSort (array, k) - это buckets ← новый массив из k пустых списков M ← максимальное значение ключа в массиве для I = 1 , к длине (массив) делают вставки массива [I] в ковши [пол (K × массив [I] / M)]  для I = 1 до K сделать nextSort (сегменты [i]) вернуть объединение сегментов [1], ...., buckets [k]

Здесь array - это массив, который нужно отсортировать, а k - количество используемых сегментов. Максимальное значение ключа можно вычислить за линейное время , просмотрев все ключи один раз. Функция floor должна использоваться для преобразования числа с плавающей запятой в целое число. Функция nextSort - это функция сортировки, используемая для сортировки каждой корзины. Обычно будет использоваться сортировка вставкой , но могут использоваться и другие алгоритмы. Использование bucketSort в качестве nextSort производит относительную сортировку radix ; в частности, случай n = 2 соответствует быстрой сортировке (хотя потенциально с плохим выбором опорных точек).

Анализ [ править ]

Анализ наихудшего случая [ править ]

Сортировка по сегментам в основном полезна, когда ввод равномерно распределяется по диапазону. Когда входные данные содержат несколько ключей, расположенных близко друг к другу (кластеризация), эти элементы, скорее всего, будут помещены в одну корзину, в результате чего некоторые корзины содержат больше элементов, чем в среднем. Наихудший сценарий возникает, когда все элементы помещаются в одну корзину. В этом случае общая производительность будет определяться алгоритмом, используемым для сортировки каждого сегмента, который обычно представляет собой сортировку вставкой , что делает сортировку сегментов менее оптимальной, чем алгоритмы сортировки сравнения , такие как сортировка слиянием .${\ Displaystyle О (п ^ {2})}$ ${\ Displaystyle О (п \ журнал (п))}$

Анализ среднего случая [ править ]

Рассмотрим случай, когда входные данные распределены равномерно. Первый шаг - инициализация сегментов и поиск максимального значения ключа в массиве - можно выполнить вовремя. Если деление и умножение можно выполнять за постоянное время, то разбрасывание каждого элемента по его ведру также стоит затрат . Предположим, что сортировка вставкой используется для сортировки каждого сегмента, тогда стоит третий шаг , где - длина проиндексированного сегмента . Поскольку мы относимся к среднему времени, вместо этого необходимо оценить ожидание . Позвольте быть случайной величиной, которая есть, если элемент помещен в корзину , и в противном случае. У нас есть . Следовательно,${\displaystyle O(n)}$${\displaystyle O(n)}$${\displaystyle O(\textstyle \sum _{i=1}^{k}\displaystyle n_{i}^{2})}$${\displaystyle n_{i}}$${\displaystyle i}$${\displaystyle E(n_{i}^{2})}$${\displaystyle X_{ij}}$${\displaystyle 1}$${\displaystyle j}$${\displaystyle i}$${\displaystyle 0}$${\displaystyle n_{i}=\sum _{j=1}^{n}X_{ij}}$

${\displaystyle {\begin{aligned}E(n_{i}^{2})&=E\left(\sum _{j=1}^{n}X_{ij}\sum _{k=1}^{n}X_{ik}\right)\\&=E\left(\sum _{j=1}^{n}\sum _{k=1}^{n}X_{ij}X_{ik}\right)\\&=E\left(\sum _{j=1}^{n}X_{ij}^{2}\right)+E\left(\sum _{1\leq j,k\leq n}\sum _{j\neq k}X_{ij}X_{ik}\right)\end{aligned}}}$

Последняя строка разделяет суммирование на случай и случай . Поскольку вероятность объекта распределяется ведро находится , составляет 1 с вероятностью , и 0 в противном случае. ${\displaystyle j=k}$${\displaystyle j\neq k}$${\displaystyle i}$${\displaystyle 1/k}$${\displaystyle X_{ij}}$${\displaystyle 1/k}$

${\displaystyle E(X_{ij}^{2})=1^{2}\cdot \left({\frac {1}{k}}\right)+0^{2}\cdot \left(1-{\frac {1}{k}}\right)={\frac {1}{k}}}$

${\displaystyle E(X_{ij}X_{ik})=1\cdot \left({\frac {1}{k}}\right)\left({\frac {1}{k}}\right)={\frac {1}{k^{2}}}}$

При суммировании это будет

${\displaystyle E\left(\sum _{j=1}^{n}X_{ij}^{2}\right)+E\left(\sum _{1\leq j,k\leq n}\sum _{j\neq k}X_{ij}X_{ik}\right)=n\cdot {\frac {1}{k}}+n(n-1)\cdot {\frac {1}{k^{2}}}={\frac {n^{2}+nk-n}{k^{2}}}}$

Наконец, сложность была бы .${\displaystyle O\left(\sum _{i=1}^{k}E(n_{i}^{2})\right)=O\left(\sum _{i=1}^{k}{\frac {n^{2}+nk-n}{k^{2}}}\right)=O\left({\frac {n^{2}}{k}}+n\right)}$

Последний шаг сортировки сегментов, который объединяет все отсортированные объекты в каждом сегменте, требует времени. Следовательно, общая сложность равна . Обратите внимание, что если k выбрано равным , тогда сортировка ведра выполняется за среднее время при равномерно распределенном вводе. ^[1]${\displaystyle O(k)}$${\displaystyle O\left(n+{\frac {n^{2}}{k}}+k\right)}$${\displaystyle k=\Theta (n)}$${\displaystyle O(n)}$

Оптимизация [ править ]

Обычная оптимизация - сначала поместить несортированные элементы сегментов обратно в исходный массив , а затем выполнить сортировку вставкой по всему массиву; поскольку время выполнения сортировки при вставке зависит от того, насколько далеко каждый элемент находится от своей конечной позиции, количество сравнений остается относительно небольшим, а иерархия памяти лучше используется путем непрерывного хранения списка в памяти. ^[2]

Варианты [ править ]

Общая сортировка по сегментам [ править ]

Наиболее распространенный вариант сортировки по сегментам работает со списком из n числовых входов от нуля до некоторого максимального значения M и делит диапазон значений на n сегментов, каждое размером M / n . Если каждый сегмент сортируется с использованием сортировки вставкой , можно показать, что сортировка выполняется за ожидаемое линейное время (где среднее значение берется по всем возможным входным данным). ^[3]Однако производительность такого рода ухудшается при кластеризации; если много значений расположены близко друг к другу, все они попадут в одну корзину и будут медленно сортироваться. Этого снижения производительности можно избежать в исходном алгоритме сортировки сегментов, предполагая, что входные данные генерируются случайным процессом, который равномерно распределяет элементы в интервале [0,1) . ^[1]

ProxmapSort [ править ]

Подобно общей сортировке сегментов, описанной выше, ProxmapSort работает, разделяя массив ключей на подмассивы с помощью функции «map key», которая сохраняет частичный порядок ключей; когда каждый ключ добавляется к своему подмассиву, сортировка вставкой используется для сохранения отсортированного подмассива, в результате чего весь массив оказывается в отсортированном порядке после завершения ProxmapSort. ProxmapSort отличается от сортировки по корзинам тем, что использует ключ карты для размещения данных примерно там, где они должны быть, в отсортированном порядке, создавая «proxmap» - сопоставление близости - ключей.

Сортировка гистограммы [ править ]

Другой вариант сортировки по сегментам, известный как сортировка по гистограмме или сортировка с подсчетом, добавляет начальный проход, который подсчитывает количество элементов, которые попадут в каждую корзину, используя массив счетчиков. ^[4] Используя эту информацию, значения массива могут быть организованы в последовательность сегментов на месте с помощью последовательности обменов, не оставляя места для хранения сегментов. ^{[ неудачная проверка ]}

Сортировка почтальона [ править ]

В своем роде Постман представляет собой вариант роторного вида , который использует преимущества иерархической структуры элементов, как правило , описывается набором атрибутов. Это алгоритм, используемый машинами для сортировки писем в почтовых отделениях : почта сначала сортируется между внутренней и международной; затем по штату, провинции или территории; затем почтовым отделением страны назначения; затем по маршрутам и т. д. Поскольку ключи не сравниваются друг с другом, время сортировки составляет O ( cn ), где c зависит от размера ключа и количества сегментов. Это похоже на сортировку по основанию счисления, которая работает «сверху вниз» или «сначала наиболее значимая цифра». ^[5]

Сортировка в случайном порядке [ править ]

Перетасовка рода ^[6] представляет собой вариант роторного рода , который начинается с удаления первого 1/8 из п элементов, подлежащих сортировке, сортирует их рекурсивно, и помещает их в массив. Это создает n / 8 "корзин", по которым распределяются оставшиеся 7/8 элементов. Затем каждое «ведро» сортируется, и «ведра» объединяются в отсортированный массив.

Сравнение с другими алгоритмами сортировки [ править ]

Сортировку по ведру можно рассматривать как обобщение сортировки с подсчетом ; фактически, если каждое ведро имеет размер 1, тогда сортировка ведра вырождается в сортировку с подсчетом. Переменный размер корзины для сортировки корзин позволяет использовать память O ( n ) вместо памяти O ( M ), где M - количество различных значений; взамен он отказывается от подсчета поведения сортировки O ( n + M ) в худшем случае.

Сортировка по сегментам с двумя сегментами, по сути, является версией быстрой сортировки, в которой значение поворота всегда выбирается как среднее значение диапазона значений. В то время как этот выбор является эффективным для равномерно распределенных входов, других средства выбора стержня в качестве быстрой сортировки , например , выбранные случайным образом поворачивается сделать его более устойчивым к кластеризации в распределении входного сигнала.

П -ходового слияние алгоритм также начинается путем распределения списка в п подсписки и сортировки каждых из них; однако подсписки, созданные с помощью сортировки слиянием, имеют перекрывающиеся диапазоны значений и поэтому не могут быть повторно объединены путем простой конкатенации, как при сортировке по корзине. Вместо этого они должны чередоваться алгоритмом слияния. Однако эти дополнительные расходы уравновешиваются более простой фазой разброса и возможностью гарантировать, что каждый подсписок имеет одинаковый размер, что обеспечивает хорошие временные рамки для наихудшего случая.

Сортировку по основанию « сверху вниз» можно рассматривать как частный случай сортировки по сегментам, когда диапазон значений и количество сегментов ограничиваются степенью двойки. Следовательно, размер каждого сегмента также является степенью двойки, и процедура может применяться рекурсивно. Этот подход может ускорить фазу разброса, поскольку нам нужно только проверить префикс битового представления каждого элемента, чтобы определить его ведро.

Ссылки [ править ]

• Пол Э. Блэк «Сортировка почтальона» из Словаря алгоритмов и структур данных в NIST .
• Роберт Рэми '"Почтальон" Журнал пользователей C, август 1992 г.
• Словарь алгоритмов и структур данных NIST: сегментная сортировка

Внешние ссылки [ править ]

• Код сортировки корзины для Ansi C
• Вариант сортировки по ведру с демонстрацией