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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук
Сортування комірками
Клас алгоритм сортування
Структура даних масив
Найгірша швидкодія
Середня швидкодія
Просторова складність у найгіршому випадку

Сортування комірками (англ. 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