傀儡的な

Inefficient recursive sorting algorithm

傀儡的な

Stooge ソートの視覚化 (スワップのみを表示)。
クラス	ソートアルゴリズム
データ構造	配列
最悪の パフォーマンス	${\displaystyle O(n^{\log 3/\log 1.5})}$
最悪の場合の 空間複雑度	${\displaystyle O(n)}$

ストゥージソートは再帰 ソートアルゴリズムです。その実行時間計算量は非常に小さいことで知られています。このアルゴリズムの実行時間は、一般的なソートアルゴリズムと比較して遅く、非効率なソートの典型例であるバブルソートよりも遅くなります。しかし、スローソートよりは効率的です。この名前は、映画『三ばか大将』に由来しています。^[1] ${\displaystyle O(n^{\log 3/\log 1.5})}$ ${\displaystyle O(n^{2.7095...})}$

アルゴリズムは次のように定義されます。

• 開始時の値が終了時の値より大きい場合は、それらを交換します。
• リストに 3 つ以上の要素がある場合は、次のようになります。
  • リストの最初の2/3をStoogeソートする
  • ストゥージはリストの最後の2/3をソートする
  • Stoogeはリストの最初の2/3を再度ソートします

再帰呼び出しで使用する整数ソート サイズを取得するには、2/3 を切り上げて取得することが重要です。たとえば、5 の 2/3 を切り上げると、3 ではなく 4 になります。そうしないと、特定のデータでソートが失敗する可能性があります。

実装

擬似コード

 function stoogesort ( array L , i = 0 , j = length ( L ) - 1 ){ if L [ i ] > L [ j ] then // 左端の要素が右端の要素より大きい場合swap ( L [ i ], L [ j ]) // それらを交換しますif ( j - i + 1 ) > 2 then // 配列に少なくとも 3 つの要素がある場合t = floor (( j - i + 1 ) / 3 ) stoogesort ( L , i , j - t ) // 配列の最初の 2/3 をソートしますstoogesort ( L , i + t , j ) // 配列の最後の 2/3 をソートしますstoogesort ( L , i , j - t ) // 配列の最初の 2/3 を再度ソートしますreturn L }                                                  

参考文献

1. "CSE 373" (PDF) . courses.cs.washington.edu . 2020年9月14日閲覧。

出典

• ブラック、ポール・E.「ストゥージ・ソート」。アルゴリズムとデータ構造の辞書。米国国立標準技術研究所。 2011年6月18日閲覧。
• トーマス・H・コーメン;チャールズ・E・ライザーソン;ロナルド・L・リベスト;スタイン、クリフォード(2001) [1990]。 「問題7-3」。アルゴリズム入門(第 2 版)。 MIT プレスとマグロウヒル。161 ～ 162ページ 。ISBN 0-262-03293-7。

外部リンク

• ソートアルゴリズム（Stoogeソートを含む）
• ストゥージソート – 実装と比較

Retrieved from "https://en.wikipedia.org/w/index.php?title=Stooge_sort&oldid=1315482240"