- Spaghetti sort
Spaghetti sort is a
linear-time , analog algorithm for sorting a sequence of items, introduced byAlexander Dewdney in his "Scientific American " column. [Citation
last = Dewdney
first = A. K.
author-link = Alexander Dewdney
title = On the spaghetti computer and other analog gadgets for problem solving
periodical =Scientific American
volume = 250
issue = 6
pages = 19-26
year = 1984
date = June 1984] [Citation
last = Stauffer
first = Dietrich
authorlink = Dietrich Stauffer
title = Annual Reviews of Computational Physics VI
publisher =World Scientific
date = May 15, 1999
page = 260
isbn = 9810235631] [Citation
last = Adamatzky
first = Andrew
authorlink = Andrew Adamatzky
title = From Utopian to Genuine Unconventional Computers
publisher =Luniver Press
date = July 1, 2006
page = 96
isbn = 0955117097] It is used as an example of quantum computing reducing the running time of generalized sorting algorithms from O(Nlog N) to O(N).Algorithm
For simplicity, assume you're sorting a list of natural numbers. The sorting method is illustrated using uncooked rods of
spaghetti :
# 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 (O(1)). This is possible because the hand, the spaghetti rods and the table work as a fully
parallel computing device. Then 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.References
External links
* [http://www.csd.uwo.ca/faculty/akd/ A. K. Dewdney's homepage]
* [http://www.bcri.ucc.ie/~dw5/download/dw20-UC06-sort.pdf Implementations of a model of physical sorting, Boole Centre for Research in Informatics]
* [http://iffwww.iff.kfa-juelich.de/~ekoch/talks/qc.pdf Classical/Quantum Computing, IFF-Institute]
Wikimedia Foundation. 2010.
