スパゲティソート

出典: フリー百科事典『ウィキペディア(Wikipedia)』
スパゲティ・ソートの模式図。台に置いたスパゲティの束から、突き出た順に取り出すことでソートができる。

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

アルゴリズム[編集]

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

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

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

つまり、棒の数が倍になれば、並べ替えに必要な時間も倍となる。これをいわゆるランダウの記号で表すと、となる。

参考文献[編集]

  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 

外部リンク[編集]