Участник:RandomAtHome/Блочная cортировка

Требуемые для зачёта пункты описания: 1.1-1.9, 2.4, 2.7, 3.

Общая схема описания алгоритмов имеет следующий вид:

1 Свойства и структура алгоритмов

Свойства алгоритмов никак не зависят от вычислительных систем, и с этой точки зрения данная часть AlgoWiki имеет безусловную собственную ценность. Описание алгоритма делается один раз, после чего многократно используется для его реализации в различных программно-аппаратных средах. Несмотря на то, что в данной части мы рассматриваем лишь машинно-независимые свойства алгоритмов, соображения, важные на этапе реализации, или же ссылки на соответствующие пункты части II AlgoWiki, здесь также вполне уместны.

1.1 Общее описание алгоритма

Блочная сортировка (Карманная сортировка, корзинная сортировка, англ. Bucket sort) — алгоритм сортировки, в котором сортируемые элементы распределяются между конечным числом отдельных блоков (карманов, корзин) так, чтобы все элементы в каждом следующем по порядку блоке были всегда больше (или меньше), чем в предыдущем. Каждый блок затем сортируется отдельно, либо рекурсивно тем же методом, либо любой другой сортировкой. Затем элементы помещаются обратно в массив. Данный алгоритм требует знаний о природе сортируемых данных, выходящих за рамки функций "сравнить" и "поменять местами", достаточных для большинства других сортировок - например сортировки слиянием, сортировки пирамидой, быстрой сортировки, сортировки Шелла, сортировки вставкой и т.д. В данном случае, дополнительные знания о данных нужны для того, чтобы правильно составить функцию распределяющую элементы по блокам, чтобы количество элементов в каждом блоке было примерно одинаковым.

Особенностью блочной сортировки является то, что она может обладать линейным временем исполнения на удачных входных данных , а также очень сильно деградировать на неудачных, в зависимости от алгоритма использующегося внутри блока сортировки. Например, в случае если блок сортируется с помощью сортировки вставками, то сложность становится равной [math]O(n^2)[/math].

Другим интересным примером является случай если число блоков [math]n = 2[/math] и используется рекурсивная блочная сортировка - тогда алгоритм, по сути, становится эквивалентен сортировке Хоара.

Лучше всего алгоритм работает, когда для входных данных удается построить функцию, равномерно распределяющую их по блокам. Хороший пример - набор чисел с фиксированной точкой равномерно распределенный на отрезке [math][0, 1)[/math]. Иными словами, сортировка отлично подходит для случаев когда данные случайны и равномерно распределены по диапазону с известными границах.

Еще стоит отметить, что в алгоритме в качестве внутренней сортировки часто используется сортировка вставками из-за некоторых ее свойств:

• Сортировка вставками может работать по мере поступления данных, в отличие от той же сортировки Хоара или сортировки слиянием
• Из-за константных множителей и членов более низкого порядка сортировка вставками может выполняться для небольших входных данных быстрее, чем другие сортировки с более низким порядком роста