Сортування коміркамиКлас |
алгоритм сортування |
---|
Структура даних |
масив |
---|
Найгірша швидкодія |
|
---|
Середня швидкодія |
|
---|
Просторова складність у найгіршому випадку |
|
Сортування комірками або коміркове сортування[1] (англ. Bucket sort) — це стабільний алгоритм впорядкування, що доцільно використовувати, якщо вхідні дані розподілені рівномірно. В основі алгоритму лежить розподілення всіх елементів по скінченній кількості комірок. Кожна комірка впорядковується окремо іншим алгоритмом впорядкування або ж рекурсивно алгоритмом впорядкування комірками. Сортування комірками є узагальненням сортування підрахунком.
Алгоритм працює за час , оскільки використовує додаткову інформацію про елементи.
Тоді як сортування підрахунком припускає, що входові дані складються з цілих чисел із маленького діапазону, сортування комірками припускає, що входові дані утворені випадковим процесом, що розподіляє елементи рівномірно і незалежно в проміжку . Процедура виконує впорядкування масиву
1
2 for to
3 do Вставити елемент в список
4 for to
5 do Впорядкувати список
6 Об'єднати списки
Аналіз складності алгоритму[ред. | ред. код]
Виконання всіх елементів алгоритму, крім рядка 5, очевидно вимагає часу. Залишається підрахувати повний час, що знадобиться на n викликів алгоритму сортування у рядку 5. Будемо вважати, що використовується алгоритм сортування вставкою.
Час роботи сортування комірками буде:
, де — кількість елементів масиву, що потрапили в i-у комірку.
Обчислимо математичне очікування:
Так як всі комірки рівноправні, то
Справедливим є запис:
Тобто, представляється сумою незалежних однаково розподілених випадкових величин. Тоді:
Підставивши результат у вираз для маємо:
Отже, очікуваний час роботи алгоритму лінійно залежить від розміру вхідного масиву.
Зауваження: середній час роботи буде лінійним навіть у випадку нерівномірного розподілу елементів масиву. Для лінійного часу необхідно лише, щоб сума квадратів кількостей елементів в кожній комірці лінійно залежала від загальної кількості елементів.
|
---|
| Теорія |
| |
---|
| Сортування обміном |
|
---|
| Сортування вибором |
|
---|
| Сортування включенням |
|
---|
| Сортування злиттям |
|
---|
| Алгоритми без порівнянь |
|
---|
| Інші |
|
---|
| Непрактичні алгоритми |
|
---|
|