[python] bogo sort (ランダムな整列)の勉強

はじめに

アルゴリズム問題の定番はsort問題だと思う。
ここではsort方法として原始的かつ基本的ではあるが、一番効率の悪いbogo sortについてまとめた。

Code

import random
from typing import List
import time


def in_order(numbers: List[int]) -> bool:
    return all(numbers[i] <= numbers[i+1] for i in range(len(numbers)-1))
    # リストのすべての要素の右側が等しいもしくは大きい場合、True でなければ False 

def bogo_sort(numbers: List[int]) -> List[int]:
    while not in_order(numbers):
        random.shuffle(numbers)
        # ランダムに要素を混ぜる
    return numbers


if __name__ == '__main__':
    start = time.time()
    nums = [random.randint(0, 1000) for _ in range(10)]
    print(bogo_sort(nums))
    print(time.time() - start)

[69, 206, 253, 355, 500, 509, 552, 591, 846, 853]
47.737563133239746

[228, 259, 323, 344, 363, 555, 564, 577, 913, 943]
38.77899479866028

[44, 67, 156, 185, 248, 452, 616, 859, 906, 936]
41.5284309387207

[122, 209, 223, 283, 311, 357, 363, 378, 707, 913]
9.765328168869019

１０個の要素をsortするのに約30~40ほどかかったことがわかる。
たまに運が良い時は10秒以下もみられた。
ｎ個の要素を並べる方法はn!個存在するので、要素が１個増えると単純に n+1 倍に時間が増えることが考えられる。

このように、非効率的な作業をコンピューターにさせないためにも、アルゴリズムの勉強をしないといけないことを実感した。