Loading article…
スパゲッティソートは、AK DewdneyがScientific Americanのコラムで紹介した、アイテムのシーケンスをソートするための線形時間アナログアルゴリズムです。[ 1 ] [ 2 ] [ 3 ]このアルゴリズムは、 O ( n )のスタックスペースを必要とするアイテムのシーケンスを安定的にソートします。並列プロセッサが必要で、並列プロセッサはO ( 1 )の時間でアイテムのシーケンスの最大値を見つけることができると想定されています。
分かりやすくするために、ここでは自然数のリストをソートすると仮定します。ソート方法は、茹でていないスパゲッティの棒を使って説明します。
n本のスパゲッティを準備するには線形時間が必要です。スパゲッティをテーブルに下ろすには定数時間O ( 1 )が必要です。これは、手、スパゲッティ、テーブルが完全に並列計算装置として機能するためです。次にn本のスパゲッティを取り除く必要があります。各接触および除去操作に定数時間がかかると仮定すると、アルゴリズムの最悪時間計算量はO ( n )になります。