ストゥージソート

出典: フリー百科事典『ウィキペディア(Wikipedia)』

移動: 案内, 検索
ストゥージソート
Sorting stoogesort anim.gif
ストゥージソートのアニメーション
クラス ソート
データ構造 配列
最悪計算時間 O(nlog 3 /log 1.5)
最悪空間計算量 O(n)

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

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

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

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


今日は何の日(10月18日

もっと見る