Сортування коміркамиКлас |
алгоритм сортування |
---|
Структура даних |
масив |
---|
Найгірша швидкодія |
![{\displaystyle O(n^{2})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6cd9594a16cb898b8f2a2dff9227a385ec183392) |
---|
Середня швидкодія |
![{\displaystyle O(n+k)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cebd2e4442e56daa59f3fab79339f952122c29e8) |
---|
Просторова складність у найгіршому випадку |
![{\displaystyle O(n\cdot k)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3ca361b07bb66f8fc594e3f6ff590b5f0690e4cd) |
Сортування комірками або коміркове сортування[1] (англ. Bucket sort) — це стабільний алгоритм впорядкування, що доцільно використовувати, якщо вхідні дані розподілені рівномірно. В основі алгоритму лежить розподілення всіх елементів по скінченній кількості комірок. Кожна комірка впорядковується окремо іншим алгоритмом впорядкування або ж рекурсивно алгоритмом впорядкування комірками. Сортування комірками є узагальненням сортування підрахунком.
Алгоритм працює за час
, оскільки використовує додаткову інформацію про елементи.
Тоді як сортування підрахунком припускає, що входові дані складються з цілих чисел із маленького діапазону, сортування комірками припускає, що входові дані утворені випадковим процесом, що розподіляє елементи рівномірно і незалежно в проміжку
. Процедура
виконує впорядкування масиву
1
2 for
to
3 do Вставити елемент
в список
4 for
to
5 do Впорядкувати список
6 Об'єднати списки
Виконання всіх елементів алгоритму, крім рядка 5, очевидно вимагає
часу. Залишається підрахувати повний час, що знадобиться на n викликів алгоритму сортування у рядку 5. Будемо вважати, що використовується алгоритм сортування вставкою.
Час роботи сортування комірками буде:
, де
— кількість елементів масиву, що потрапили в i-у комірку.
Обчислимо математичне очікування:
Так як всі комірки рівноправні, то
Справедливим є запис:
Тобто,
представляється сумою незалежних однаково розподілених випадкових величин. Тоді:
Підставивши результат у вираз для
маємо:
Отже, очікуваний час роботи алгоритму лінійно залежить від розміру вхідного масиву.
Зауваження: середній час роботи буде лінійним навіть у випадку нерівномірного розподілу елементів масиву. Для лінійного часу необхідно лише, щоб сума квадратів кількостей елементів в кожній комірці лінійно залежала від загальної кількості елементів.
|
---|
| Теорія |
| |
---|
| Сортування обміном |
|
---|
| Сортування вибором |
|
---|
| Сортування включенням |
|
---|
| Сортування злиттям |
|
---|
| Алгоритми без порівнянь |
|
---|
| Інші |
|
---|
| Непрактичні алгоритми |
|
---|
|