スパゲティソート

ウィキペディア

スパゲティソート

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2023/06/18 19:58 UTC 版)

スパゲティ・ソートの模式図。台に置いたスパゲティの束から、突き出た順に取り出すことでソートができる。

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

アルゴリズム

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

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

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

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

参考文献

1. ^ Dewdney, A. K. (June 1984), “On the spaghetti computer and other analog gadgets for problem solving”, Scientific American 250 (6): 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 

外部リンク

• A. K. Dewdney's homepage
• Implementations of a model of physical sorting, Boole Centre for Research in Informatics

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