Photo by
chicori_3_3
#7 ソートアルゴリズム バブルソート
使うことが少なくても基本は大事よね。
バブルソート
隣り合う要素の大小を比較しながら整列させるソートアルゴリズム。
アルゴリズムが単純で実装も容易である一方、最悪時間計算量は O(n2) と遅いため、一般にはマージソートやヒープソートなど、より最悪時間計算量の小さな（従って高速な）方法が利用される。
全ての要素に関して比較交換が行なわれるならば順序を問わない特徴を持つ
隣り合うデータを比べて並べ替えるというシンプルなソートです。
最悪な計算時間が降順になっているデータを昇順にするなどの常に入れアケが生じるパターンで$${O(n^2)}$$の計算量です。
逆に入れ替えが生じないケース、一度データの並べ替えのループを行って終わる場合は計算量nで終わります。
このバブルソートを改良したアルゴリズムもあることからまず基本のソートアルゴリズムとして学びます。
コード
コードはシンプル二重ループで隣り合うデータを比較してます。
def bubble_sort(lists):
print('元データ:',lists)
n=len(lists)
cnt=0
for i in range(0,n-1):
for j in range(n-1,i,-1):
if lists[j-1] > lists[j]:
lists[j],lists[j-1] = lists[j-1],lists[j]
cnt += 1
print(lists,i+1)
print('ソート後:',lists)
print('入れ替え回数',cnt)
def gen_val(n):
return [r.randint(0,1000) for i in range(0,n)]
if __name__ == "__main__":
a=gen_val(10)
start=t.time()
bubble_sort(a)
print(t.time()-start)
結果
結果を見ると並べ替え回数が23回と多いことがわかると思います。
データの並びによって、並べ替え回数、処理時間が変わるのでどのようなデータの配列では時間がかかるのか、かからないのか試すのも良いでしょう。
元データ: [998, 753, 190, 874, 7, 349, 246, 766, 910, 682]
[7, 998, 753, 190, 874, 246, 349, 682, 766, 910] 1
[7, 190, 998, 753, 246, 874, 349, 682, 766, 910] 2
[7, 190, 246, 998, 753, 349, 874, 682, 766, 910] 3
[7, 190, 246, 349, 998, 753, 682, 874, 766, 910] 4
[7, 190, 246, 349, 682, 998, 753, 766, 874, 910] 5
[7, 190, 246, 349, 682, 753, 998, 766, 874, 910] 6
[7, 190, 246, 349, 682, 753, 766, 998, 874, 910] 7
[7, 190, 246, 349, 682, 753, 766, 874, 998, 910] 8
[7, 190, 246, 349, 682, 753, 766, 874, 910, 998] 9
ソート後: [7, 190, 246, 349, 682, 753, 766, 874, 910, 998]
入れ替え回数 23
0.024322032928466797
参考書籍
いいなと思ったら応援しよう！
