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

Шаблон:Картка алгоритм Сортування комірками або коміркове сортування (Шаблон:Lang-en) — це стабільний алгоритм впорядкування, що доцільно використовувати, якщо вхідні дані розподілені рівномірно. В основі алгоритму лежить розподілення всіх елементів по скінченній кількості комірок. Кожна комірка впорядковується окремо іншим алгоритмом впорядкування або ж рекурсивно алгоритмом впорядкування комірками. Сортування комірками є узагальненням сортування підрахунком.

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

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

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

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

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

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

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

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

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

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

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

$n_i=\sum _{j=1}^n{\chi }_{ij},{\chi }_{ij}=\{\begin{array}{cc}1& ,A[i]\in B[j]\\ 0\end{array}$

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

$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[\sum _{j=1}^n{\chi }_{ij}^2+\sum _{j=1}^n\sum _{1\le k\le n,k\ne j}^n{\chi }_{ij}{\chi }_{ik}]=$

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

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

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

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

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

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