スパゲティソートのソースを表示

[[File:Spaghetti sort.gif|thumb|スパゲティ・ソートの模式図。台に置いたスパゲティの束から、突き出た順に取り出すことでソートができる。]]

'''スパゲティソート''' (Spaghetti sort) はコンピュータ科学における[[ソート|並べ替え]]の[[アルゴリズム]]の一種。一般には使われることがない思考上のアルゴリズムである。数学者で作家の{{仮リンク|A. K. デュードニー|en|A. K. Dewdney}}が考案した<ref>{{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
| date = June 1984}}</ref><ref>{{Citation
| last = Stauffer
| first = Dietrich
| authorlink = Dietrich Stauffer
| title = Annual Reviews of Computational Physics VI
| publisher = {{仮リンク|World Scientific|en|World Scientific|label=World Scientific}}
| date = May 15, 1999
| page = 260
| isbn = 981-02-3563-1}}</ref><ref>{{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 = 0-9551170-9-7}}</ref>。スパゲティソートの平均計算時間は、データ数が<math>n</math>倍になると、<math>n</math>倍になる。また、デュードニーがこのソートの説明を乾燥スパゲティを長さ順に並べ替える手順に例えたことで知られる。

==アルゴリズム==
アルゴリズム考案者のデュードニー自身が、スパゲティの並べ替えに例えて説明している。

# 長さが不揃いの乾燥スパゲティの束があったとする。これを手で軽く握ってテーブルの表面に立てる。
# 次に、もう一方の手を上から降ろしていき、最初に触った棒を取り出す。これが一番長い棒となる。この棒をリストの最初に追加する。さらに手を降ろしていき、次に触れた棒をリストの2番目に追加する。全ての棒が無くなるまで、この手順を繰り返す。

これをコンピュータアルゴリズムとして使う場合、並べ替えに必要な時間として、(1)与えられた数列と同じ長さのスパゲティを準備する時間、(2)スパゲティを並べ替える時間、(3)並べたスパゲティを数字に変換する時間が挙げられる。これらの時間は全てスパゲティの本数に比例する。

つまり、棒の数が<math>n</math>倍になれば、並べ替えに必要な時間も<math>n</math>倍となる。これをいわゆる[[ランダウの記号]]で表すと、<math>O(n)</math>となる。
これは、一般的なソートアルゴリズムの時間計算量が<math>O(n^2)</math>や<math>O(n \log n)</math>である（[[ソート#ソートアルゴリズムの一覧]]）ことを考えると、珍しい特性である。

==参考文献==
{{Reflist}}

==外部リンク==
* [http://www.csd.uwo.ca/faculty/akd/ A. K. Dewdney's homepage]
* [http://www.dna.caltech.edu/~woods/download/dw20-UC06-sort.pdf Implementations of a model of physical sorting, Boole Centre for Research in Informatics]

{{ソート}}

{{DEFAULTSORT:すはけていそと}}
[[Category:ソート]]