ストゥージソート（）は、再帰を用いたソートアルゴリズムのひとつである。
計算時間はであり、これはマージソートなどの効率的なアルゴリズムよりも、それどころか非常に効率の悪い単純なソートの例としてよく挙げられるバブルソートよりも遅い。
アルゴリズムは以下の通りである。 もし末尾の値が先頭の値より小さければ、それらを入れ替える。 現在処理している部分列の要素数が3以上であれば、 リストの先頭2/3この2/3の操作は切り上げで行う。切り捨てにより行うと特定のデータで失敗する。例えば、数列{3,4,5,1,2}を切り捨てにより昇順にストゥージソートすると数列{1,2,4,3,5}が返され不正となる。に対してストゥージソートを行う。 リストの末尾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
脚注
参考文献
Cormen, Thomas H.; Leiserson, Charles E., Rivest, Ronald L., Stein, Clifford (2001) . "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