ボゴソート

Sorting algorithm

ボゴソート

クラス	ソート
データ構造	配列
最悪の場合の パフォーマンス	無制限（ランダム化バージョン）、（決定論的バージョン） ${\displaystyle O(n\times n!)}$
最高の パフォーマンス	${\displaystyle \Omega (n)}$[1]
平均的な パフォーマンス	${\displaystyle \Theta (n\times n!)}$[1]
最悪の場合の 空間複雑度	${\displaystyle \mathrm {O} (1)}$

コンピュータサイエンスにおいて、ボゴソート^{[1] [2] （}順列ソート、愚かなソート^[3]とも呼ばれる）は、生成とテストのパラダイムに基づくソートアルゴリズムである。この関数は、入力の順列を連続的に生成し、ソート済みの順列が見つかるまで繰り返す。ソートにはあまり役立たないと考えられているが、より効率的なアルゴリズムと対比させるため、教育目的で使用されることがある。このアルゴリズムの名前は、bogus（偽）とsort（ソート）を組み合わせた造語である。^[4]

このアルゴリズムには2つのバージョンがあります。1つは、ソートされた順列に出会うまですべての順列を列挙する決定論的バージョン^{[2] [5]}、もう1つは、入力をランダムに順列化し、ソートされているかどうかを確認するランダム化バージョンです。後者の動作は、トランプの山札を空中に投げ、ランダムにカードを拾い上げ、この処理を繰り返すことでトランプの山札をソートするようなものです。このバージョンでは、最悪のシナリオとして、乱数源の品質が低く、ソートされた順列が発生する可能性が低くなることがあります。

確率分析

ボゴソートは主に非効率的なソートアルゴリズムの教育的な例として議論されていますが、基本的な確率論にも関連付けることができます。

予想される動作を分析する一つの方法は、ランダムシャッフルを繰り返した後にソートされた配列が得られる確率を考えることです。これは、一連の独立した試行において少なくとも1回の成功確率を表す一般的な式に類似しています。

${\displaystyle P({\text{at least one success}})=1-(P({\text{failure in one trial}}))^{n}}$

ここで、は独立したシャッフル（試行）回数を表します。ボゴソートの文脈では、「成功」はソートされた順列を生成することに対応し、「失敗」はソートされていない順列 を生成することに対応します。可能な順列のうち1つだけがソートされているため、1回の試行で成功する確率は です。したがって、シャッフル回数内でソートされたリストが得られる確率は、次のようになります。 ${\displaystyle n}$ ${\displaystyle n!}$ ${\displaystyle 1/n!}$ ${\displaystyle k}$

${\displaystyle P({\text{sorted within }}k{\text{ shuffles}})=1-\left(1-{\tfrac {1}{n!}}\right)^{k}}$

この枠組みはボゴソートの極度の非効率性を浮き彫りにしている。たとえ の値が適度であっても、が天文学的に大きくない限り、成功確率は極めて小さいままである。^{[6] [7]} ${\displaystyle n}$ ${\displaystyle k}$

アルゴリズムの説明

擬似コード

以下は、擬似コードによるランダム化アルゴリズムの説明です。

function bogoSort(deck: List ): デッキがソートされていない場合: シャッフル（デッキ）

C

Cでの実装:

#include <stdio.h> #include <stdlib.h> #include <time.h>   void shuffle ( int a [], int length ) { int temp ; int random ; for ( size_t i = 0 ; i < size ; i ++ ) { random = rand () % length ; temp = a [ random ]; a [ random ] = a [ i ]; a [ i ] = temp ; } }                                  [[ nodiscard ]] bool sorted ( int a [], int length ) { for ( size_t i = 0 ; i < length - 1 ; i ++ ) { if ( a [ i ] > a [ i + 1 ]) { return false ; } } return true ; }                              void bogoSort ( int a [], int length ) { while ( ! sorted ( a , length )) { shuffle ( a , length ); } }            int main ( int argc , char * argv []) { // 使用例int input [] = { 68 , 14 , 78 , 98 , 67 , 89 , 45 , 90 , 87 , 78 , 65 , 74 }; int size = sizeof ( input ) / sizeof ( int );                            // 疑似乱数ジェネレータを初期化するsrand ( time ( NULL ));  bogoSort (入力,サイズ);  // ソートされた結果: 14 45 65 67 68 74 78 78 87 89 90 98 printf ( "ソートされた結果: " ); for ( size_t i = 0 ; i < size ; i ++ ) { printf ( " %d" , input [ i ]); } printf ( " \n " );                0を返す; } 

パイソン

Pythonでの実装:

ランダムにインポート # この関数は配列がソートされているかどうかを確認しますdef is_sorted ( a : list [ int ]) -> bool : for i in range ( 1 , len ( a )): if a [ i ] < a [ i - 1 ]: return False return True                   # この関数は、配列の要素がソートされるまで繰り返しシャッフルします。def bogo_sort ( a : list [ int ]) -> list [ int ]: while not is_sorted ( random_array ): random . shuffle ( random_array ) return random_array          # この関数はランダムに選択された整数値を持つ配列を生成します。def generate_random_array ( size : int , min_val : int , max_val : int ) -> list [ int ]: return [ random . randint ( min_val , max_val ) for _ in range ( size )]               if  __name__  ==  "__main__" :  # ランダムに生成された配列のサイズ、最小値、最大値 size :  int  =  10  min_val :  int  =  1  max_val :  int  =  100  random_array :  list [ int ]  =  generate_random_array ( size ,  min_val ,  max_val )  print ( "Unsorted array:" ,  random_array )  sorted_arr  =  bogo_sort ( random_array )  print ( "Sorted array:" ,  sorted_arr )

このコードは、generate_random_array でランダム配列（random_array）を作成し、bogosort でシャッフルしてソートします。配列内のすべてのデータは1から100までの自然数です。

実行時間と終了

ボゴソートの実験的実行時間

ソートするすべての要素が異なっている場合、ランダム化ボゴソートによって平均的に実行される比較の期待値はに漸近的に等しく 、平均的に行われるスワップの期待値は に等しくなります。^[1]スワップの期待値は比較の期待値よりも速く増加します。これは、要素が順序付けられていない場合、要素の数に関係なく、通常、数回の比較でこれが発見されるためです。ただし、コレクションをシャッフルする作業は、そのサイズに比例します。最悪の場合、コインを投げたときに何度でも表が出ることがあるのと同じ理由で、比較とスワップの数はどちらも無制限です。 ${\displaystyle (e-1)n!}$ ${\displaystyle (n-1)n!}$

最良のケースは、与えられたリストがすでにソートされている場合です。この場合、予想される比較回数は であり、スワップはまったく実行されません。^[1] ${\displaystyle n-1}$

固定サイズのコレクションの場合、無限サル定理が成り立つのとほぼ同じ理由で、アルゴリズムの予想実行時間は有限です。つまり、正しい順列を得る確率がいくらかあるため、無制限の回数試行すると、最終的にはほぼ確実に正しい順列が選択されます。

関連アルゴリズム

ゴロソート

2011年のGoogle Code Jamで導入されたソートアルゴリズム。^[8]リストが順序付けられていない限り、すべての要素のサブセットがランダムに並べ替えられる。このサブセットが毎回最適に選択される場合、この操作を実行する必要がある合計回数の期待値は、誤って配置された要素の数に等しい。

ボゴボゴソート

リストの先頭から小さなコピーを徐々に小さくしていき、それらがソートされているかどうかを確認するアルゴリズム。基本ケースは単一の要素であり、常にソートされている。それ以外のケースでは、最後の要素と、リスト内の前の要素の中で最大の要素を比較する。最後の要素がより大きいか等しい場合、コピーの順序が前のバージョンと一致するかどうかを確認し、一致する場合は戻る。そうでない場合は、リストの現在のコピーをシャッフルし、再帰チェックを再開する。^[9]

ボゾソート

乱数に基づく別のソートアルゴリズムです。リストが順序付けられていない場合、ランダムに2つの項目を選択し、それらを入れ替えて、リストがソートされているかどうかを確認します。ボゾソートの実行時間分析はより困難ですが、H. Gruberによる「ひどくひどい」ランダムソートアルゴリズムの分析でいくつかの推定値が記載されています。^[1] は、期待される平均的なケースであることがわかっています。 ${\displaystyle O(n!)}$

ワーストソート

有限時間内に完了することが保証されている悲観的なソートアルゴリズムですが、設定によっては効率がかなり悪くなることがあります。 このアルゴリズムは、悪いソートアルゴリズム に基づいています。この悪いソート アルゴリズムは、ソート対象のリスト と再帰の深さ の2 つのパラメータを受け入れます。再帰レベル では、はバブルソートなどの一般的なソート アルゴリズムを使用して入力をソートし、ソートされたリストを返します。つまり、 です。したがって、 の場合、悪いソートの時間計算量は です。ただし、任意の に対して、はまずのすべての順列のリストを生成します。次にを計算し、ソートされた の最初の要素を返します。を本当に悲観的にするために、を次のような計算可能な増加関数の値に割り当てることができます(たとえば、はアッカーマン関数です)。したがって、リストをかなり悪くソートするには、 を実行します。ここでは の要素数です。結果として得られるアルゴリズムの複雑度は であり、ここで=反復回数の階乗である。このアルゴリズムは、十分に速く増加する関数 を選択することで、望むだけ非効率にすることができる。^[10] ${\displaystyle {\texttt {worstsort}}}$ ${\displaystyle {\texttt {badsort}}}$ ${\displaystyle L}$ ${\displaystyle k}$ ${\displaystyle k=0}$ ${\displaystyle {\texttt {badsort}}}$ ${\displaystyle {\texttt {badsort}}(L,0)={\texttt {bubblesort}}(L)}$ ${\displaystyle O(n^{2})}$ ${\displaystyle k=0}$ ${\displaystyle k>0}$ ${\displaystyle {\texttt {badsort}}(L,k)}$ ${\displaystyle P}$ ${\displaystyle L}$ ${\displaystyle {\texttt {badsort}}}$ ${\displaystyle {\texttt {badsort}}(P,k-1)}$ ${\displaystyle P}$ ${\displaystyle {\texttt {worstsort}}}$ ${\displaystyle k}$ ${\displaystyle f:\mathbb {N} \to \mathbb {N} }$ ${\displaystyle f(n)=A(n,n)}$ ${\displaystyle A}$ ${\displaystyle {\texttt {worstsort}}(L,f)={\texttt {badsort}}(f({\texttt {length}}(L)))}$ ${\displaystyle {\texttt {length}}(L)}$ ${\displaystyle L}$ ${\textstyle \Omega \left(\left(n!^{(f(n))}\right)^{2}\right)}$ ${\displaystyle n!^{(m)}=(\dotso ((n!)!)!\dotso )!}$ ${\displaystyle n}$ ${\displaystyle m}$ ${\displaystyle f}$

スローソート

大規模な複雑さを実現するために誤った分割統治戦略を採用した、一風変わったユーモラスなソート アルゴリズムです。

量子ボゴソート

ボゴソートに基づく仮説的なソートアルゴリズム。コンピュータ科学者の間で内輪のジョークとして考案された。このアルゴリズムは、量子エントロピー源を用いて入力のランダムな順列を生成し、リストがソートされているかどうかを確認し、ソートされていない場合は宇宙を破壊する。多世界解釈が成り立つと仮定すると、このアルゴリズムを使用すると、入力が時間的にソートされた宇宙が少なくとも1つは生き残ることになる。^[11] ${\displaystyle O(n)}$

参照

• ラスベガスアルゴリズム
• 傀儡的な

参考文献

1. Gruber, H.; Holzer, M.; Ruepp, O. (2007)、「Sorting the slow way: an analysis of perversely awesome randomized sorting algorithms」、第4回International Conference on Fun with Algorithms、Castiglioncello、イタリア、2007年(PDF)、Lecture Notes in Computer Science、vol. 4475、Springer-Verlag、pp.  183– 197、doi :10.1007/978-3-540-72914-3_17、ISBN 978-3-540-72913-6。
2. Kiselyov, Oleg; Shan, Chung-chieh; Friedman, Daniel P.; Sabry, Amr (2005), "Backtracking, interleaving, and terminating monad transformers: (functional pearl)", Proceedings of the Tenth ACM SIGPLAN International Conference on Functional Programming (ICFP '05) (PDF) , SIGPLAN Notices, pp.  192– 203, doi :10.1145/1086365.1086390, S2CID 1435535, 2012年3月26日時点のオリジナル(PDF) からアーカイブ, 2011年6月22日閲覧
3. ES Raymond. 「bogo-sort」.『The New Hacker's Dictionary』. MIT Press, 1996.
4. "bogosort". xlinux.nist.gov . 2020年11月11日閲覧。
5. Naish, Lee (1986)、「NU-Prologにおける否定と量指定子」、第3回国際論理プログラミング会議論文集、コンピュータサイエンス講義ノート、第225巻、Springer-Verlag、pp.  624– 634、doi :10.1007/3-540-16492-8_111、ISBN 978-3-540-16492-0。
6. Bobbitt, Zach (2021年1月5日). 「「少なくとも1回」の成功の確率を調べる方法」Statology . 2025年10月6日閲覧。
7. メジャー、レスリー、ゴールドリスト、エイミー（2024年4月1日）。「X件以上のイベントを計算する」 {{cite journal}}:ジャーナルを引用するには|journal=（ヘルプ）が必要です
8. Google Code Jam 2011、予選ラウンド、問題 D
9. ボゴボゴソート
10. Lerma, Miguel A. (2014). 「ソートアルゴリズムはどの程度非効率になるか？」arXiv : 1406.1077 [cs.DS].
11. The Other Tree (2009年10月23日). 「Quantum Bogosort」(PDF) . MathNEWS . 111 (3): 13. 2020年7月5日時点のオリジナルよりアーカイブ(PDF) . 2022年3月20日閲覧。

外部リンク

• WikiWikiWebの BogoSort
• 非効率的なソートアルゴリズム
• Bogosort:標準のソートプログラムに似た、 Unix 系システムで実行される実装。
• Bogosort と jmmcg::bogosort: bogosort アルゴリズムのシンプルだが奇妙な C++ 実装。
• Bogosort NPM パッケージ: Node.js エコシステム用の bogosort 実装。
• マックス・シャーマン ボゴソートはちょっと遅い、2013年6月

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