ボゴソート

ボゴソート

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

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

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

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

デッキがソートされていない場合:
    シャッフル（デッキ）

C での実装:

#include <stdio.h> 
#include <stdlib.h> 
#include <time.h> 

// 指定された配列に対してインプレース bogo ソートを実行します
静的void bogo_sort ( int * a 、intサイズ);     
// 指定された配列がソートされている場合は 1 を返し、そうでない場合は 0 を返します
静的int is_sorted ( int * a 、intサイズ);     
// 指定された配列をランダムな順序にシャッフルします
静的voidシャッフル( int * a 、intサイズ);     

void bogo_sort ( int * a , intサイズ) {     
    while ( ! is_sorted ( a 、size )) {   
        シャッフル( a 、サイズ); 
    }
}

int is_sorted ( int * a , intサイズ) {     
    ( int i = 0 ; i <サイズ-1 ; i ++ ) {​         
        もし( a [ i ] > a [ i + 1 ] ) {    
            0 を返します。 
        }
    }
    1を返します。 
}

voidシャッフル( int * a , intサイズ) {     
    int temp 、ランダム;  
    ( int i = 0 ; i <サイズ; i ++ ) {​         
        ランダム= ( int ) (( double ) rand () / (( double ) RAND_MAX + 1 ) *サイズ);           
        temp = a [ランダム];  
        a [ランダム] = a [ i ];  
        a [ i ] =一時;  
    }
}

intメイン（）{  
    // 使用例
    int入力[ ] = { 68、14、78、98、67、89、45、90、87、78、65、74 } ;​​​​​​​​​​​​​​​​​​​​                
    intサイズ= sizeof (入力) / sizeof ( *入力);     

    // 疑似乱数ジェネレータを初期化する
    srand (時間( NULL ) );

    bogo_sort (入力,サイズ); 

    // ソートされた結果: 14 45 65 67 68 74 78 78 87 89 90 98
    printf ( "ソートされた結果:" );
    ( int i = 0 ; i <サイズ; i ++ ) {​         
        printf ( " %d " ,入力[ i ]); 
    }
    printf ( " \n " );

    0 を返します。 
}

Python 3での実装:

 ランダムにインポート

# この関数は配列がソートされているかどうかをチェックします
def  is_sorted ( random_array ): 
  for  i  in  range ( 1 ,  len ( random_array ) ): 
    if  random_array [ i ]  <  random_array [ i  -  1 ]: 
      return  False 
  return  True

# この関数は、配列の要素がソートされるまで繰り返しシャッフルします
def  bogo_sort ( random_array ): 
  while  not  is_sorted ( random_array ): 
    random . shuffle ( random_array ) 
  return  random_array

# この関数はランダムに選択された整数値を持つ配列を生成します
def  generate_random_array ( size ,  min_val ,  max_val ): 
  return  [ random . randint ( min_val ,  max_val )  for  _  in  range ( size )]

# ランダムに生成された配列のサイズ、最小値、最大値
size  =  10 
min_val  =  1 
max_val  =  100 
random_array  =  generate_random_array ( size 、 min_val 、 max_val ) 
print ( "未ソートの配列:" 、 random_array ) 
sorted_arr  =  bogo_sort ( random_array ) 
print ( "ソートされた配列:" 、 sorted_arr )

このコードでは、 がdataPython の組み込みのような単純で変更可能な配列のようなデータ構造であり、listその要素を問題なく比較できることを前提としています。

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

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

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

ゴロソート

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

ボゴボゴソート

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

ボゾソート

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

ワーストソート

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

スローソート

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

量子ボゴソート

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

奇跡のソート

奇跡が起こるまで配列がソートされているかどうかをチェックするソートアルゴリズム。配列がソートされるまで継続的に配列をチェックし、配列の順序は決して変更しません。^[10]順序は決して変更されないので、アルゴリズムの仮想的な時間計算量はO ( ∞ )ですが、それでも奇跡やシングルイベントアップセットなどのイベントをソートすることができます。最適化コンパイラはこれを単純にwhile(true)ループに変換する可能性があるため、このアルゴリズムの実装には特に注意する必要があります。ただし、最良のケースはO ( n )であり、これはソートされたリストで発生します。比較のみを行うため、厳密にインプレースかつ安定しています。

ボゾボゴソート

リストがすでに整列している場合にのみ機能するソート アルゴリズム。そうでない場合は、ミラクル ソートの条件が適用されます。

神の類

リストを受け取り、リストが現在の順列でランダムに発生する確率が非常に低い (1/n! の確率、n は要素の数) ため、リストの順序には理由があるに違いないと判断するソート アルゴリズム。したがって、このリストは、私たちが理解できない方法でソートされているとみなされるべきであり、あたかも「神が意図したとおり」にソートされているかのように、私たちの信念に従ってソートする権利はありません。インテリジェント デザイン ソートとも呼ばれます。^[11]

• ラスベガスアルゴリズム
• 傀儡の類

Wikibookアルゴリズム実装には、ボゴソートに関するページがあります。

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