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

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

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

Алгоритм

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

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

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

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

Ссылки

Spaghetti sort on Wikipedia

Добавить комментарий