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

Автор - студент 401 группы факультета ВМК Чухарев Фёдор Сергеевич.

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

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

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

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

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

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

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

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

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

1.2 Математическое описание алгоритма

Пусть у нас есть массив из [math]n[/math] элементов распределенных равномерно в каком-то неизвестном нам диапазоне и [math]k[/math] блоков, по которым мы распределяем эти элементы. Оценим среднее время работы алгоритма блочной сортировки для случая, при котором в качестве алгоритма сортировки блоков используется сортировка вставками.

Первый шаг - проиницилизировать блоки, найдя наибольший и наименьший элементы. Это возможно сделать за [math]O(n)[/math], за один проход по массиву. Второй шаг, распределение элементов по блокам, вообще говоря, тоже занимает [math]O(n)[/math] времени. Так как мы предположили, что внутренней сортировкой является сортировка вставками, то внутренняя сортировка займет [math]O(\textstyle \sum_{i=1}^k \displaystyle n_i^2)[/math] времени, где [math]n_i[/math] - размер блока с индексом [math]i[/math]. Так как мы считаем среднее время, то надо вычислить математическое ожидание [math]E(n_i^2)[/math].

Введем случайную величину [math]X_{ij}[/math], которая равна 1, если A[j] попадает в i-й карман, и 0 в противном случае. Очевидно, что [math]n_i = \sum_{j=1}^n X_{ij}[/math]. Тогда,

[math]\begin{align} 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{align} [/math]

В последней строчке сумма разделяется на случай [math]j=k[/math] и случай [math]j\neq k[/math]. Так как вероятность того, что элемент попадет в блок с индексом [math]i[/math] равна [math]1/k[/math], [math]X_{ij} [/math] равна 1 с вероятностью [math]1/k[/math] и равна 0 иначе.

[math]E(X_{ij}^2) = 1^2\cdot \left(\frac{1}{k}\right) + 0^2\cdot \left(1-\frac{1}{k}\right) = \frac{1}{k}[/math]

[math]E(X_{ij}X_{ik}) = 1\cdot \left(\frac{1}{k}\right)\left(\frac{1}{k}\right) = \frac{1}{k^2} [/math]

Подставим эти выражения в сумму и получим:

[math]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}[/math]

Следовательно, вычислительная сложность алгоритма равна [math]O\left(\sum_{i=1}^kE(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) [/math].

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