ボゴソートをPHPで実装した

ボゴソートとは

とても効率の悪い最凶アルゴリズムの一つと言われているボゴソート。
ランダムに並べたデータを順番にチエックして、順番に並んでいなければシャッフルを再度行う。
よく例えられるのはバラバラにしたトランプが順番に並んでいるかを繰り返すというとんでもないアルゴリズムです。

Wikipedia ボゴソート

ソースコード解説

  • classをインスタンスした時にランダムな配列データを生成
  • bogoSorting()でデータが順番に並んでいなければシャッフルを行いbogoSorting()を再帰的に呼び出す
  • データが順番に並んでいることが確認されたら再帰呼出しを抜ける

とても効率の悪いものになっています。

挙句データの量を増やしていくと7個を超えたあたりから、
何故かセグメンテーション違反が頻繁に起きるようになってきました。。。

結論

そももそなんで5個のデータを繰り返しシャッフルしているだけなのに500回もハズレを引かないといけないんだよというのも疑問に出てきます、そうすると疑うべきはPHPのshuffle関数と再帰呼出しを延々と呼び出した時に何故か出るセグメンテーション違反のエラー。

最近だと並列処理を使ってクイックソートよりも優れたアルゴリズムというのもあるそうですが・・・
なんとも後味の悪い結果になってしまいました。

コメントを残す