Відкрити головне меню

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

Сортування комірками
Клас алгоритм сортування
Структура даних масив
Найгірша швидкодія
Середня швидкодія
Просторова складність у найгіршому випадку

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

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

Тоді як сортування підрахунком припускає, що входові дані складються з цілих чисел із маленького діапазону, сортування комірками припускає, що входові дані утворені випадковим процесом, що розподіляє елементи рівномірно і незалежно в проміжку  . Процедура   виконує впорядкування масиву  

 
1    
2 for   to  
3         do Вставити елемент   в список  
4 for   to  
5         do Впорядкувати список  
6 Об'єднати списки  

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

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

Час роботи сортування комірками буде:  , де   — кількість елементів масиву, що потрапили в i-у комірку.

Обчислимо математичне очікування:  

 

Так як всі комірки рівноправні, то  

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

 

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

 

 

 

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

 

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

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

ДжерелаРедагувати

  • Thomas H. Cormen; Charles E. Leiserson; Ronald L. Rivest; Clifford Stein. Introduction to Algorithms (2nd ed.) The MIT Press. ISBN 0-07-013151-1