ボゴソート単語

ボゴソート

ボゴソート(英: bogosort, bogo-sort, bogo sort)とは、ソートアルゴリズムの一種である。

概要

ソートの対トランプとすると、

  1. トランプシャッフルする。
  2. きちんと順番になってるかどうかを調べる。
  3. 順番になっていれば終了。なっていなければ1に戻る。

というこの上なくらしい冗談のようなソートアルゴリズム。ちなみにボゴ(bogo- < bogus)とは「偽、いんちき」といった意味であり、冗談のようなどころか本当に冗談である。

無限の猿定理により必ずソートできることが保されてはいるものの、気が遠くなるほどの時間がかかることも事実で、均計算時間は O(n×n!) 、最悪計算時間は 。数あるソートアルゴリズムの中でも最低の性である。
このため、stupid sort, slowsort, monkey sort (以上、サルでもできる愚鈍なソート)、random sort, shotgun sort (以上、下手なも数撃ちゃ当たるソート)とも呼ばれている。

しかしながら、最良計算時間は O(n) という、クイックソートえるほぼ理論値であるため、今後量子コンピュータクラスの並列処理が可になればクイックソートを抑えて脚を浴びるとか浴びないとか言われている隠れた有望でもある。

実装自体はランダムブチ撒けるだけでありそれほど難しくないように思えるが、乱数というコンピュータにとって苦手な分野を扱うために性のいい乱数発生器が必要不可欠であり、乱数発生器に性の大部分を依存するので理論的にはまだまだ効率追求の余地がある。

関連動画

 

関連商品

ボゴソートに関するニコニコ市場の商品を紹介してください。

関連コミュニティ

ボゴソートに関するニコニコミュニティを紹介してください。

関連項目

【スポンサーリンク】

スマホ版URL:
https://dic.nicovideo.jp/t/a/%E3%83%9C%E3%82%B4%E3%82%BD%E3%83%BC%E3%83%88

この記事の掲示板に最近描かれたお絵カキコ

お絵カキコがありません

この記事の掲示板に最近投稿されたピコカキコ

ボゴソート

16 ななしのよっしん
2015/06/19(金) 19:43:24 ID: VU9ggIVgfg
分かりやすく言えば、
人ぐらいいるボゴソートたんに同時にソートして貰えば一発ソートできるってわけだな!
17 ななしのよっしん
2015/06/20(土) 23:56:32 ID: P6hzECKg1n
お前ら!これ運良ければ一発ソートできんだぞ!最強だろ!!!
運が良ければな!!!
18 ななしのよっしん
2015/06/21(日) 09:03:22 ID: BMdNJrDmWw
>>9-10
重複チェックを入れると、それまでの結果を全て記憶せにゃならんし、
試行回数が増えるにつれてチェックの手間も膨大になっていくので、
むしろチェックを入れない方がシンプルで効率がいいんじゃないかな
19 ななしのよっしん
2015/06/24(水) 21:05:16 ID: kOcAH0n9jC
TASさんなら最速ってコメに笑った
20 ななしのよっしん
2015/06/25(木) 22:16:23 ID: qj1HBRzYgZ
ボゴソートくん

タイトル:ボゴソートくん

twitterで紹介する

21 ななしのよっしん
2015/06/26(金) 17:56:13 ID: ZMkPfy8S/t
ボゴソートかっけえええええええええええええええええ
22 ななしのよっしん
2016/01/02(土) 11:58:24 ID: WjRUUDqxZB
量子計算機でボゴソートした場合、並列に投入するまではいいとして、結果ちゃんとソートされているものを取り出すのはどうやってやるんだろう
23 ななしのよっしん
2016/04/01(金) 19:55:49 ID: xZYaFI5c+p
>>22
める結果が昇順(1, 2, ..., 10)だとして、a[n] <= a[n+1]が常に成立するような結果を戻してくればいいのでは
24 ななしのよっしん
2016/10/25(火) 22:20:39 ID: XzOiLARfg8
細かいことだけど
概要の(行合わせて)12行の後のほう
randamでなくrandomですよね
プレミアムさんお願いします()
25 ななしのよっしん
2018/08/23(木) 12:51:16 ID: SY7CNXVntA
ボゴソートのゆかいな仲間たち 英語版wikipediaより引用
Gorosort(ゴロソート) ニアピン賞的なやつ
1. トランプ2組を用意して、それぞれをシャッフル
2. どちらの束がより整列されているかを
3a. 時間がまだあるなら、整列されていない方の束をシャッフルして2.に戻る
3b. 時間切れになったら、一番よく整列された束をソート結果とする
時間内に全なソートができる保はない。

Bogobogosort(ボゴボソート) 賽の河原的なやつ
1. トランプ1組をシャッフル
2. 山札を上から順に見ていき、ソートされているか確認する
3. 上からn枚が正しくソートされていなければ、上からn枚をシャッフルして2.に戻る
(省略しています。全て読むにはこのリンクをクリック!)

急上昇ワード