ストゥージソート

ストゥージソートのアニメーション
クラス	ソート
データ構造	配列
最悪計算時間	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]に対して再びストゥージソートを行う。
• そうでなければ終了。

 algorithm stoogesort(array L, i = 0, j = length(L)-1)
     if L[j] < L[i] then
         L[i] ↔ L[j]
     if (j - i + 1) >= 3 then
         t = (j - i + 1) / 3
         stoogesort(L, i  , j-t)
         stoogesort(L, i+t, j  )
         stoogesort(L, i  , j-t)
     return L

• Black, Paul E.. “stooge sort”. Dictionary of Algorithms and Data Structures. National Institute of Standards and Technology. 2011年6月18日閲覧。
• Cormen, Thomas H.; Leiserson, Charles E., Rivest, Ronald L., Stein, Clifford (2001) [1990]. "Problem 7-3". Introduction to Algorithms (2nd ed.). MIT Press and McGraw-Hill. pp. 161-162. ISBN 0-262-03293-7.

• Everything2.com - Stooge sort
• Sorting Algorithms (including Stooge sort)
• Stooge sort - implementation and comparison

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