Startup Web3.0 Data scientist's Blog

データサイエンスとメタバースの情報を発信します

pythonを使ったバブルソートアルゴリズムの実装

バブルソートとは

ソートアルゴリズムの中の一つのアルゴリズムバブルソートは、隣り合う要素の大小を比較しながら整列させるソートアルゴリズムアルゴリズムが単純で実装も容易である一方、最悪時間計算量は 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]

さらに次の記述で、左右の場所を入れ替えています。