データ構造とアルゴリズム:Bogoソート
bogo(ボゴソート)
ボゴソートはシャッフルに並び替えた後にそのソートが正しく並び替えられているかを確認するソート手法。
def in_order
では、左側の数字が右側の数字(i+1番目)よりも大きければその時点で並び替えは失敗しているので、return Falseという
配列の1つ目から、forで回して、最後の1個以外を一つ後に来る配列の要素と大きさを比べている。 最後の要素までいったということが配列が正しく並び替えられている理由になるので、最後の一個は比較しない。
in_orderがTrueを返すまではランダムに並び替える作業を止めないので、while not
文でTrueが返ってくるまでランダムシャッフルと並び替えの確認作業をし続ける。
import random from typing import list def in_order(numbers): for i in range(len(numbers) - 1): if numbers[i] > numbers[i+1]: return False return True def bogo_sort(numbers): while not in_order(numbers): random.shuffle(numbers) return numbers if __name__ == '__main__': print(bogo_sort([1, 5, 3, 2, 6])) [1, 2, 3, 5, 6]
in_order
の確認はリスト内包括を利用することで1文で書くことができる。
def in_order(numbers: List[int]) -> bool: return all(numbers[i] <= numbers[i + 1] for i in range(len(numbers) - 1)) def bogo_sort(numbers: list) -> list: while not in_order(numbers): random.shuffle(numbers) return numbers if __name__ == '__main__': print(bogo_sort([1, 5, 3, 2, 6]))
def bogo_sort(numbers: List[int) -> List[int]:
と書くことで、引数にlist型を期待していて、返り値にinteger型のlistを返すということを明示できる。 listの代わりにboolなども使用可能。
詳しくはなんかぐぐる↓ 実践!!Python型入門(Type Hints)
ランダムな配列を適当に作るコード
0 ~ 100までのランダムな数字で10個の要素を持つ配列を作成する。
if __name__ == '__main__': nums = [random.randint(0, 100) for _ in range(10)] print(nums) [21, 97, 13, 36, 89, 59, 30, 50, 14, 15]
このようにbogoソートはランダムで実行するので、基本的に処理時間は長い。運が良ければ処理時間が短くなるが可能性はひくい。下記、ボゴソートを行った時の処理時間を測定。 配列が100個あるときは終わらなかった。。。
# 配列が10この時 [17, 26, 31, 31, 49, 51, 64, 69, 76, 89] 4.3439563389993054
Pythonの if name == 'main': は何のためにあるものですか?
この構文がないと、単にimportされた時にも.pyファイルが実行されてしまうので、import時の実行を防ぐために記載される処理。