ストゥージソート

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

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

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

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

実装

脚注

参考文献

• 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