バブルソートとは、与えられた数列を昇順または降順に並び替えるアルゴリズムの一種です。高速化のためにCで書きたかったのですが、pythonの方がわかりやすいのでpythonで書いてみます。
目次
アルゴリズム概要
バブルソートアルゴリズムはかなりシンプルだと思います。
左または右から数列をスキャンしていき、i番目とi+1番目の数の大きさを比べた結果によって数列を並べ替えていきます。一回の走査で数列全域をスキャンすることになるので、最悪計算量はO(n**2)となります。
実装
import random
class Seq:
def __init__(self)-> None:
self.seq = [i+1 for i in range(100)]
def set(self):
return random.sample(self.seq,len(self.seq))
def is_not_sorted(seq):
for i in range(len(seq)-1):
if seq[i]>seq[i+1]:
return True
else:
pass
return False
seq = Seq()
#1から100までの数をランダムに並び替えた数列を生成します。
seq = seq.set()
print(seq)
＃バブルソートを行います。
def bubble_sort(seq):
while is_not_sorted(seq):
for i in range(len(seq)-1):
if seq[i]>seq[i+1]:
seq[i],seq[i+1]=seq[i+1],seq[i]
else:
pass
return seq並び替えがまだ必要かどうかを判定するために、１ループにつき余計にもう一周スキャンしているのでもっといい方法がないか考えます。
