ストゥージソートとは? わかりやすく解説

Weblio 辞書 > 辞書・百科事典 > 百科事典 > ストゥージソートの意味・解説 

ストゥージソート

(Stooge sort から転送)

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2021/01/09 20:11 UTC 版)

ナビゲーションに移動 検索に移動
ストゥージソート
ストゥージソートのアニメーション
クラス ソート
データ構造 配列
最悪計算時間 O(nlog 3 /log 1.5)
最悪空間計算量 O(n)

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

計算時間はO(nlog 3 / log 1.5 ) = O(n2.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

脚注

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

参考文献

外部リンク





英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「ストゥージソート」の関連用語

ストゥージソートのお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



ストゥージソートのページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアのストゥージソート (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。

©2025 GRAS Group, Inc.RSS