Спагетти сорт
 | Эта статья может сбивать с толку или быть непонятной читателям . ( Июль 2013 г. ) |
Сортировка спагетти это К. — аналоговый алгоритм сортировки А. последовательности элементов с линейным временем, представленный Дьюдни в его колонке в журнале Scientific American . [1] [2] [3] сортирует последовательность элементов, требующих O ( n Этот алгоритм стабильно ) стекового пространства. Для этого требуется параллельный процессор.
Алгоритм
[ редактировать ]Для простоты предположим, что мы сортируем список натуральных чисел . Метод сортировки проиллюстрирован на примере сырых стержней спагетти :
- Для каждого числа x в списке получите стержень длины x . (Один практический способ выбора единицы измерения — сделать так, чтобы наибольшее число m в списке соответствовало одному полному стержню спагетти. В этом случае полный стержень равен m единицам спагетти. Чтобы получить стержень длины x , сломайте стержень два так, чтобы одна часть имела длину x единиц, другую часть отбросьте.)
- Собрав все палочки для спагетти, свободно возьмите их в кулак и опустите на стол так, чтобы все они стояли вертикально и опирались на поверхность стола. Теперь для каждого стержня опускайте другую руку сверху до тех пор, пока она не встретится со стержнем — этот явно самый длинный. Удалите этот стержень и вставьте его в начало (изначально пустого) выходного списка (или, что то же самое, поместите его в последний неиспользуемый слот выходного массива). Повторяйте, пока все стержни не будут удалены.
Анализ
[ редактировать ]Приготовление n палочек спагетти занимает линейное время. Опускание стержней на стол занимает постоянное время O ( 1 ). Это возможно, потому что рука, палочки для спагетти и стол работают как полностью параллельное вычислительное устройство. Тогда необходимо удалить n стержней, поэтому, предполагая, что каждая операция контакта и удаления занимает постоянное время, временная сложность алгоритма в худшем случае равна O ( n ).
Ссылки
[ редактировать ]- ^ Дьюдни, А.К. (июнь 1984 г.), «О компьютере-спагетти и других аналоговых устройствах для решения проблем», Scientific American , vol. 250, нет. 6, стр. 19–26.
- ^ Штауффер, Дитрих (15 мая 1999 г.), Ежегодные обзоры вычислительной физики VI , World Scientific , стр. 260, ISBN 981-02-3563-1
- ^ Адамацкий, Эндрю (1 июля 2006 г.), От утопических к настоящим нетрадиционным компьютерам , Luniver Press , стр. 96, ISBN 0-9551170-9-7