ストゥージソート

クラス ソート

データ構造 配列

最悪計算時間 O(n^{log 3 /log 1.5})

最悪空間計算量 O(n)

ストゥージソート

ストゥージソートのアニメーション
クラス	ソート
データ構造	配列
最悪計算時間	O(nlog 3 /log 1.5)
最悪空間計算量	O(n)

ストゥージソート（英: Stooge sort）は、再帰を用いたソートアルゴリズムのひとつである。

計算時間はO(n^{log 3 / log 1.5} ) = O(n^2.7095...)であり、これはマージソートなどの効率的なアルゴリズムよりも、それどころか非常に効率の悪い単純なソートの例としてよく挙げられるバブルソートよりも遅い。

アルゴリズムは以下の通りである。

• もし末尾の値が先頭の値より小さければ、それらを入れ替える。
• 現在処理している部分列の要素数が3以上であれば、
  • リストの先頭2/3^[1]に対してストゥージソートを行う。
  • リストの末尾2/3^[1]に対してストゥージソートを行う。
  • リストの先頭2/3^[1]に対して再びストゥージソートを行う。
• そうでなければ終了。