Карманная сортировка
В данной статье будет описан алгоритм карманной сортировки, а так же приведён пример реализации алгоритма на паскале. Карманную сортировку так же называют блочной или корзинной.Карманная сортировка — алгоритм сортировки, в котором сортируемые элементы распределяются между конечным числом отдельных блоков (карманов) так, чтобы все элементы в каждом следующем по порядку блоке были всегда больше (или меньше), чем в предыдущем. Каждый блок затем сортируется отдельно, либо рекурсивно карманной сортировкой, либо другим. Затем элементы помещаются обратно в массив. Этот тип сортировки может обладать линейным временем исполнения.
Алгоритм карманной сортировки требует знаний о природе сортируемых данных, выходящих за рамки функций "сравнить" и "поменять местами", достаточных для сортировки слиянием, сортировки пирамидой, быстрой сортировки, сортировки Шелла, сортировки вставкой.
Первый этап карманной сортировки: распределение по карманам
Второй этап карманной сортировки: сортировка карманов и восстановление массива.
Преимущества:
Алгоритм карманной сортировки относится к классу быстрых алгоритмов с линейным временем исполнения O(N) (на удачных входных данных).
Недостатки:
Алгоритм карманной сортировки сильно деградирует при большом количестве мало отличных элементов, или же на неудачной функции получения номера корзины по содержимому элемента.
Пример карманной сортировки на паскале (pascal)