Bogosort
これまでに多くの問題でソートされたリストを扱ってきました。配列をソートするときは組み込み関数を利用してきましたが、それらの関数が内部でどのように動いているかは明確ではありません。そこで本章では、用途に応じてさまざまな場面で使用される代表的なソートアルゴリズムをいくつか取り上げます。
最初に紹介するのは、すべてのソートアルゴリズムの中でも最もばかげたものです。その名も Bogosort。実際のアプリケーションではまったく使われておらず、その理由はすぐに分かるでしょう。
n 個の数字が与えられたとき、このアルゴリズムは数字をランダムに並べ替え、その結果得られたリストがソート済みかどうかを確認します。from random import shuffle
a = [3, 1, -2, 5, 6] # 初期の数
while True: # 配列がソートされるまでループ
is_sorted = True
for i in range(1, len(a)): # 配列がソートされているか確認するループ
if a[i] < a[i-1]: # 前の要素よりも小さい要素がある場合、ソートされていない
is_sorted = False # 変数をFalseにしてループを抜ける
break
if is_sorted: # 配列がソートされていれば無限ループを終了
break
else: # そうでなければもう一度リストをシャッフルする
shuffle(a)
print(a) # 最終的なリストを出力このアルゴリズムはランダム要素が強く、完了までに無限の時間がかかる可能性があります。したがって、実際のアプリケーションで使うのは危険かつ非効率的です。
ここでは、Bogosort アルゴリズムが最終的に解を見つけるまでに要する反復回数を求めるよう求められています。
入力
最初の行に単一の整数
n (1 ≤ n ≤ ) が与えられます。次の行には
n 個の整数 ( ≤ ≤ ) が空白区切りで与えられます。出力
Bogosort アルゴリズムが探索を完了するまでにかかる反復回数を出力します。
例
入力 | 出力 |
5
5 -1 2 3 9 | 10 |
解説
ここでの 10 はランダムな結果です。同じ入力でも、実行するたびに 2 や 200 といった異なる値が出る可能性があります。
他のばかげたソートアルゴリズム
Ardens が制作した以下の YouTube 動画で、他の可視化されたソートアルゴリズムを確認できます。
Constraints
Time limit: 60 seconds
Memory limit: 512 MB
Output limit: 1 MB