アルゴリズムの勉強 #1 bogo sort

概要

1. リストがソートされているかどうかを確認する
2. ソートされていない場合は、ランダム入れ替える

リストがソートされるまで、手順を繰り返し続けます。

特徴など

ソートアルゴリズムの中でも非常に効率が悪いことで知られている

計算量

Best (最良計算時間)

O(n)

・まぐれでシャッフルして、順番通り並んでいたならそうなる

Average (平均計算時間）

O(n・n!)

Worst (最悪計算時間)

O(∞)

・一生終わらない

実装例

Python 3.9.6

import random

def in_order(numbers: list[int]) -> bool:
    # for i in range(len(numbers) - 1):
    #     if numbers[i] > numbers[i + 1]:
    #         return False
    # return True
    return all(numbers[i] <= numbers[i + 1] for i in range(len(numbers) - 1))

def bogo_sort(numbers: list[int]) -> list[int]:
    random.shuffle(numbers)
    while not in_order(numbers):
        random.shuffle(numbers)
    return numbers

if __name__ == '__main__':
    nums = [random.randint(1, 1000) for _ in range(10)]
    # nums = [1, 2, 3, 4, 5]
    print(bogo_sort(nums))

その他メモ

・別名
　　・monkey sort（猿でもできるソート）
　　・random sort
　　・shotgun sort