スパゲティソート

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

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

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

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

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

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