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

Аналоговый параллельный алгоритм, сортирующий набор положительных чисел за линейное время.

Идея та же что и у спящей сортировки.

Алгоритм

Представим каждое число в виде стержня сухого спагетти соответствующей длины. Установим спагетти вертикально на ровной поверхности (например, держа их пучком или каким-то иным способом).Сверху на спагетти опускается пресс. Каждый раз когда пресс будет ломать очередной стержень, фиксируем очередной отсортированный элемент.

Характеристики алгоритма

НазваниеСпагетти-сортировка (Spaghetti sort)
АвторАлександр Дьюдни (Alexander Dewdney)
Год1984
КлассПараллельные сортировки
УстойчивостьДа
СравненияНет
Сложность по времениO(n)

Ссылки

Spaghetti sort