スパゲティソート

スパゲティソート (Spaghetti sort) はコンピュータ科学における並べ替えのアルゴリズムの一種。一般には使われることがない思考上のアルゴリズムである。数学者で作家のが考案した。スパゲティソートの平均計算時間は、データ数がformula_1倍になると、formula_1倍になる。また、デュードニーがこのソートの説明を乾燥スパゲティを長さ順に並べ替える手順に例えたことで知られる。
アルゴリズム.
アルゴリズム考案者のデュードニー自身が、スパゲティの並べ替えに例えて説明している。
これをコンピュータアルゴリズムとして使う場合、並べ替えに必要な時間として、(1)与えられた数列と同じ長さのスパゲティを準備する時間、(2)スパゲティを並べ替える時間、(3)並べたスパゲティを数字に変換する時間が挙げられる。これらの時間は全てスパゲティの本数に比例する。
つまり、棒の数がformula_1倍になれば、並べ替えに必要な時間もformula_1倍となる。これをいわゆるランダウの記号で表すと、formula_5となる。
これは、一般的なソートアルゴリズムの時間計算量がformula_6やformula_7である（ソート#ソートアルゴリズムの一覧）ことを考えると、珍しい特性である。