バブルソートとは
ソートアルゴリズムの中の一つのアルゴリズム。バブルソートは、隣り合う要素の大小を比較しながら整列させるソートアルゴリズム。 アルゴリズムが単純で実装も容易である一方、最悪時間計算量は O(n2) と遅いため、一般にはマージソートやヒープソートなど、より最悪時間計算量の小さな(従って高速な)方法が利用される。
pythonを使ったサンプルコード
def bubble_sort(data):
for i in range(1, len(data)):
for j in range(0, len(data)-i):
if data[j] > data[j+1]:
data[j], data[j+1] = data[j+1], data[j]
if __name__ == '__main__':
data = [5,4,3,2,-1]
bubble_sort(data)
print(data)
>>>
[-1, 2, 3, 4, 5]
for i in range(1,len(data)):
リスト内の要素を何回操作するのか設定しています。len関数でリストの要素個数を設定しています。
for j in range(0, len(data)-i):
操作回数を設定しています。len関数を使用することでデータ内で何回操作(ソート)する必要があるのかカウントします。
iは隣り合う要素と比較する回数を示しており、操作回数はi-1回で表記されます。
if data[j] > data[j+1]:
左を右を比較するように記述しています。
data[j], data[j+1] = data[j+1], data[j]
さらに次の記述で、左右の場所を入れ替えています。