Spaghetti sort
Encyclopedia
Spaghetti sort is a linear-time, analog
algorithm
for sorting a sequence of items, introduced by Alexander Dewdney
in his Scientific American
column.
:
(1). This is possible because the hand, the spaghetti rods and the table work as a fully parallel computing
device. There are then n rods to remove so, assuming each contact-and-removal operation takes constant time, the worst-case time complexity of the algorithm is O(n).
The space complexity is also minimal: O(n), measured in rods of spaghetti.
Analog computer
An analog computer is a form of computer that uses the continuously-changeable aspects of physical phenomena such as electrical, mechanical, or hydraulic quantities to model the problem being solved...
algorithm
Sorting algorithm
In computer science, a sorting algorithm is an algorithm that puts elements of a list in a certain order. The most-used orders are numerical order and lexicographical order...
for sorting a sequence of items, introduced by Alexander Dewdney
Alexander Dewdney
Alexander Keewatin Dewdney is a Canadian mathematician, computer scientist and philosopher who has written a number of books on the future and implications of modern computing. He has also written one work of fiction, The Planiverse...
in his Scientific American
Scientific American
Scientific American is a popular science magazine. It is notable for its long history of presenting science monthly to an educated but not necessarily scientific public, through its careful attention to the clarity of its text as well as the quality of its specially commissioned color graphics...
column.
Algorithm
For simplicity, assume you're sorting a list of natural numbers. The sorting method is illustrated using uncooked rods of spaghettiSpaghetti
Spaghetti is a long, thin, cylindrical pasta of Italian origin. Spaghetti is made of semolina or flour and water. Italian dried spaghetti is made from durum wheat semolina, but outside of Italy it may be made with other kinds of flour...
:
- 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 your 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, simply 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.
Analysis
Preparing the n rods of spaghetti takes linear time. Lowering the rods on the table takes constant time, OBig O notation
In mathematics, big O notation is used to describe the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions. It is a member of a larger family of notations that is called Landau notation, Bachmann-Landau notation, or...
(1). This is possible because the hand, the spaghetti rods and the table work as a fully parallel computing
Parallel computing
Parallel computing is a form of computation in which many calculations are carried out simultaneously, operating on the principle that large problems can often be divided into smaller ones, which are then solved concurrently . There are several different forms of parallel computing: bit-level,...
device. There are then n rods to remove so, assuming each contact-and-removal operation takes constant time, the worst-case time complexity of the algorithm is O(n).
The space complexity is also minimal: O(n), measured in rods of spaghetti.