Сортування комірками

Сортування комірками або коміркове сортування^[1] (англ. Bucket sort) — це стабільний алгоритм впорядкування, що доцільно використовувати, якщо вхідні дані розподілені рівномірно. В основі алгоритму лежить розподілення всіх елементів по скінченній кількості комірок. Кожна комірка впорядковується окремо іншим алгоритмом впорядкування або ж рекурсивно алгоритмом впорядкування комірками. Сортування комірками є узагальненням сортування підрахунком.

Сортування комірками

Клас	алгоритм сортування
Структура даних	масив
Найгірша швидкодія	${\displaystyle O(n^{2})}$
Середня швидкодія	${\displaystyle O(n+k)}$
Просторова складність у найгіршому випадку	${\displaystyle O(n\cdot k)}$

Алгоритм працює за час ${\displaystyle O(N)}$, оскільки використовує додаткову інформацію про елементи.

Псевдокод алгоритму

Тоді як сортування підрахунком припускає, що входові дані складються з цілих чисел із маленького діапазону, сортування комірками припускає, що входові дані утворені випадковим процесом, що розподіляє елементи рівномірно і незалежно в проміжку ${\displaystyle [0,1)}$. Процедура ${\displaystyle \;Bucket\_Sort(A)}$ виконує впорядкування масиву ${\displaystyle A\;}$

${\displaystyle \;Bucket\_Sort(A)}$
1 ${\displaystyle n\leftarrow length[A]}$  
2 for ${\displaystyle i\leftarrow 1}$ to ${\displaystyle \;n}$
3         do Вставити елемент ${\displaystyle \;A[i]}$ в список ${\displaystyle \;B[\lfloor nA[i]\rfloor ]}$
4 for ${\displaystyle i\leftarrow 0}$ to ${\displaystyle \;n-1}$
5         do Впорядкувати список ${\displaystyle \;B[i]}$
6 Об'єднати списки ${\displaystyle \;B[0],B[1],...,B[n-1]}$

Аналіз складності алгоритму

Виконання всіх елементів алгоритму, крім рядка 5, очевидно вимагає ${\displaystyle \;O(n)}$ часу. Залишається підрахувати повний час, що знадобиться на n викликів алгоритму сортування у рядку 5. Будемо вважати, що використовується алгоритм сортування вставкою.

Час роботи сортування комірками буде: ${\displaystyle T(n)=\Theta (n)+\sum _{i=0}^{n-1}O\left(n_{i}^{2}\right)}$, де ${\displaystyle n_{i}}$ — кількість елементів масиву, що потрапили в i-у комірку.

Обчислимо математичне очікування: ${\displaystyle M[T(n)]=M\left[\Theta (n)+\sum _{i=0}^{n-1}O\left(n_{i}^{2}\right)\right]=}$

${\displaystyle =\Theta (n)+M\left[\sum _{i=0}^{n-1}O\left(n_{i}^{2}\right)\right]=\Theta (n)+\sum _{i=0}^{n-1}O\left(M\left[n_{i}^{2}\right]\right)}$

Так як всі комірки рівноправні, то ${\displaystyle M\left[n_{i}^{2}\right]=F(n),\forall i}$

Справедливим є запис:

${\displaystyle n_{i}=\sum _{j=1}^{n}\chi _{ij},\quad \chi _{ij}={\begin{cases}1&,A[i]\in B[j]\\0\end{cases}}}$

Тобто, ${\displaystyle n_{i}}$ представляється сумою незалежних однаково розподілених випадкових величин. Тоді:

${\displaystyle M\left[n_{i}^{2}\right]=M\left[\left(\sum _{j=1}^{n}\chi _{ij}\right)^{2}\right]=M\left[\sum _{j=1}^{n}\sum _{k=1}^{n}\chi _{ij}\chi _{ik}\right]=M\left[\sum _{j=1}^{n}\chi _{ij}^{2}+\sum _{j=1}^{n}\sum _{1\leq k\leq n,k\neq j}^{n}\chi _{ij}\chi _{ik}\right]=}$

${\displaystyle =\sum _{j=1}^{n}M\left[\chi _{ij}^{2}\right]+\sum _{j=1}^{n}\sum _{1\leq k\leq n,k\neq j}^{n}M\left[\chi _{ij}\chi _{ik}\right]=\sum _{j=1}^{n}{\frac {1}{n}}+\sum _{j=1}^{n}\sum _{1\leq k\leq n,k\neq j}^{n}M\left[\chi _{ij}\right]M\left[\chi _{ik}\right]=}$

${\displaystyle =1+n(n-1){\frac {1}{n^{2}}}=1+{\frac {n-1}{n}}=2-{\frac {1}{n}}}$

Підставивши результат у вираз для ${\displaystyle T(n)}$ маємо:

${\displaystyle M[T(n)]=\Theta (n)+\sum _{i=0}^{n-1}O\left(2-{\frac {1}{n}}\right)=\Theta (n)+O(n)=\Theta (n)}$

Отже, очікуваний час роботи алгоритму лінійно залежить від розміру вхідного масиву.

Зауваження: середній час роботи буде лінійним навіть у випадку нерівномірного розподілу елементів масиву. Для лінійного часу необхідно лише, щоб сума квадратів кількостей елементів в кожній комірці лінійно залежала від загальної кількості елементів.