ストゥージソート

ストゥージソート
ストゥージソートのアニメーション
クラス	ソート
データ構造	配列
最悪計算時間	O(n^{log 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

脚注

^ ^a ^b ^c この2/3の操作は切り上げで行う。切り捨てにより行うと特定のデータで失敗する。例えば、数列{3,4,5,1,2}を切り捨てにより昇順にストゥージソートすると数列{1,2,4,3,5}が返され不正となる。

参考文献

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ソートアンシャッフルソート（英語版）
その他	トポロジカルソートパンケーキソートスパゲティソート
非効率的/ ユーモラスソート	ボゴソートストゥージソートスリープソートエラーソート
カテゴリ