ストゥージソート
![]() ストゥージソートのアニメーション | |
クラス | ソート |
---|---|
データ構造 | 配列 |
最悪計算時間 | O(nlog 3 /log 1.5) |
最悪空間計算量 | O(n) |
ストゥージソート(英: Stooge sort)は、再帰を用いたソートアルゴリズムのひとつである。
計算時間はO(nlog 3 / log 1.5 ) = O(n2.7095...)であり、これはマージソートなどの効率的なアルゴリズムよりも、それどころか非常に効率の悪い単純なソートの例としてよく挙げられるバブルソートよりも遅い。
アルゴリズムは以下の通りである。
- もし末尾の値が先頭の値より小さければ、それらを入れ替える。
- 現在処理している部分列の要素数が3以上であれば、
- そうでなければ終了。
実装
[編集] 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
理論 | |
---|---|
交換ソート | |
選択ソート | |
挿入ソート | |
マージソート |
|
非比較ソート | |
並行ソート | |
混成ソート | |
その他 | |
非効率的/ ユーモラスソート | |
![]() |
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.