Bogo Sortとは
Bogo Sort（ボゴソート）とは、非効率で非実用的なソートアルゴリズムのひとつ。非安定なソートの一種。
ソートとしてこれを指すことはほぼない。教育目的やアルゴリズムの理解を深めるために用いられることがある。
アルゴリズム
- 適当に並び替える
- ソートが完了しているか確認する
- 完了していなければ1に戻る
実装例
import random
def is_sorted(numbers: list[int]) -> bool:
return all(numbers[i] <= numbers[i + 1] for i in range(len(numbers) - 1))
def bogo_sort(numbers: list[int]) -> list[int]:
sorted_list = numbers.copy()
while not is_sorted(sorted_list):
random.shuffle(sorted_list)
return sorted_list計算量
要素数を$n$とする。
| 計算量 | |
|---|---|
| Average | $\mathrm{O}((n+1)!)$ |
| Best | $\mathrm{O}(n)$ |
| Worst | Unbounded |
Pros
- アルゴリズムが単純
Cons
- 極端に非効率。実用的なソートアルゴリズムとしてはまったく適さない。
- 実行時間が不定。理論上、ソートが完了するまでに無限の時間がかかりうる。
- 計算リソースを無駄に消費する
- 非安定なソート
利用場面
- 教育目的 : 効率的なソートアルゴリズムと比較することで、アルゴリズムの理解を深められる