スパゲティソート

スパゲティソート (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)}$である（ソート#ソートアルゴリズムの一覧）ことを考えると、珍しい特性である。