Спагетти-сортировка :: Spaghetti sort

Аналоговый параллельный алгоритм, сортирующий набор положительных чисел за линейное время.
Идея та же что и у спящей сортировки.
Алгоритм
Представим каждое число в виде стержня сухого спагетти соответствующей длины. Установим спагетти вертикально на ровной поверхности (например, держа их пучком или каким-то иным способом).Сверху на спагетти опускается пресс. Каждый раз когда пресс будет ломать очередной стержень, фиксируем очередной отсортированный элемент.
Характеристики алгоритма
Название | Спагетти-сортировка (Spaghetti sort) | |
---|---|---|
Автор | Александр Дьюдни (Alexander Dewdney) | |
Год | 1984 | |
Класс | Параллельные сортировки | |
Устойчивость | Да | |
Сравнения | Нет | |
Сложность по времени | O(n) |