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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[math]\displaystyle{ \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]\displaystyle{ j=k }[/math] и случай [math]\displaystyle{ j\neq k }[/math]. Так как вероятность того, что элемент попадет в блок с индексом [math]\displaystyle{ i }[/math] равна [math]\displaystyle{ 1/k }[/math], [math]\displaystyle{ X_{ij} }[/math] равна 1 с вероятностью [math]\displaystyle{ 1/k }[/math] и равна 0 иначе.

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

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

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

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

Следовательно, вычислительная сложность алгоритма равна [math]\displaystyle{ 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]\displaystyle{ O(k) }[/math] времени. Следовательно, общая сложность алгоритма равна [math]\displaystyle{ O\left(n+\frac{n^2}{k}+k\right) }[/math]. Если k выбрать как некоторую функцию от [math]\displaystyle{ n }[/math], [math]\displaystyle{ k = \Theta(n) }[/math], то вообще говоря среднее время будет равно [math]\displaystyle{ O(n) }[/math], при условии что входные данные равномерно распределены.