Введение
Линейное время, аналоговый алгоритм сортировки последовательности элементов.
Спагетти-сортировка — это аналоговый алгоритм сортировки последовательности элементов с линейной временной сложностью, представленный А. К. Дьюдни в его колонке в журнале Scientific American. Этот алгоритм сортирует последовательность элементов, требуя O(n) места в стеке и обеспечивая стабильную сортировку. Для его работы требуется параллельный процессор.
Алгоритм
Для простоты, предположим, что мы сортируем список натуральных чисел. Метод сортировки иллюстрируется с использованием невареных палочек спагетти: для каждого числа x в списке возьмите палочку длиной x. (Один из практических способов выбора единицы измерения – соотнести наибольшее число m в списке с одной полной палочкой спагетти. В этом случае полная палочка равна m единицам спагетти. Чтобы получить палочку длиной x, сломайте палочку на две части так, чтобы одна часть была длиной x единиц; вторую часть отбросьте.) Когда у вас будут все палочки, возьмите их в кулак и опустите на стол, чтобы они стояли вертикально, опираясь на поверхность стола. Теперь, для каждой палочки, опустите другую руку сверху, пока она не коснется палочки – эта, очевидно, самая длинная. Удалите эту палочку и поместите её в начало (первоначально пустого) выходного списка (или, что эквивалентно, в последний свободный элемент выходного массива). Повторяйте, пока не удалите все палочки.
For each number x in the list, obtain a rod of length x. (One practical way of choosing the unit is to let the largest number m in the list correspond to one full rod of spaghetti. In this case, the full rod equals m spaghetti units. To get a rod of length x, break a rod in two so that one piece is of length x units; discard the other piece.) Once you have all your spaghetti rods, take them loosely in your fist and lower them to the table, so that they all stand upright, resting on the table surface. Now, for each rod, lower your other hand from above until it meets with a rod—this one is clearly the longest. Remove this rod and insert it into the front of the (initially empty) output list (or equivalently, place it in the last unused slot of the output array). Repeat until all rods have been removed.
Анализ
Приготовление n палочек спагетти занимает линейное время. Опускание палочек на стол занимает постоянное время, O(1). Это возможно, потому что рука, палочки спагетти и стол работают как полностью параллельное вычислительное устройство. Затем нужно убрать n палочек, поэтому, предполагая, что каждая операция контакта и удаления занимает постоянное время, временная сложность алгоритма в худшем случае составляет O(n).