スパゲティソート

スパゲティソート (Spaghetti sort) はコンピュータ科学における並べ替えのアルゴリズムの一種。一般には使われることがない思考上のアルゴリズムである。数学者で作家のA. K. デュードニー（英語版）が考案した^[1]^[2]^[3]。スパゲティソートの平均計算時間は、データ数が $n$ 倍になると、 $n$ 倍になる。また、デュードニーがこのソートの説明を乾燥スパゲティを長さ順に並べ替える手順に例えたことで知られる。

アルゴリズム

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

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

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

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

参考文献

^ Dewdney, A. K. (June 1984), “On the spaghetti computer and other analog gadgets for problem solving”, Scientific American 250 (6): pp. 19–26
^ Stauffer, Dietrich (May 15, 1999), Annual Reviews of Computational Physics VI, World Scientific（英語版）, p. 260, ISBN 981-02-3563-1
^ Adamatzky, Andrew (July 1, 2006), From Utopian to Genuine Unconventional Computers, Luniver Press, p. 96, ISBN 0-9551170-9-7

外部リンク

[1] Dewdney, A. K. (June 1984), “On the spaghetti computer and other analog gadgets for problem solving”, Scientific American 250 (6): pp. 19–26

[2] Stauffer, Dietrich (May 15, 1999), Annual Reviews of Computational Physics VI, World Scientific（英語版）, p. 260, ISBN 981-02-3563-1

[3] Adamatzky, Andrew (July 1, 2006), From Utopian to Genuine Unconventional Computers, Luniver Press, p. 96, ISBN 0-9551170-9-7

[1]

[2]

[3]

表話編歴ソート
理論	計算複雑性理論ランダウの記号全順序リスト安定性ソーティングネットワーク比較ソート（英語版）整数ソート（英語版）
交換ソート	バブルソートシェーカーソート奇偶転置ソートコムソートノームソートクイックソート
選択ソート	選択ソートヒープソートスムースソートデカルト木ソートトーナメントソート
挿入ソート	挿入ソートシェルソートツリーソート図書館ソートペイシェンスソート
マージソート	マージソート多層マージソートストランドソート
非比較ソート	基数ソートバケットソート計数ソートプロキシマップソート鳩の巣ソートバーストソートビーズソート
並行ソート	バイトニックソートバッチャー奇偶マージソートシェアソート
混成ソート	ティムソートイントロソート Jソートアンシャッフルソート（英語版）
その他	トポロジカルソートパンケーキソートスパゲティソート
非効率的/ ユーモラスソート	ボゴソートストゥージソートスリープソートエラーソート
カテゴリ