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