『Pythonで体験してわかるアルゴリズムとデータ構造』メモその5/バブルソートを改良しよう
『Pythonで体験してわかるアルゴリズムとデータ構造』を読みながらアルゴリズムについて勉強する。
- 作者: 西澤弘毅,森田光
- 出版社/メーカー: 近代科学社
- 発売日: 2018/06/30
- メディア: 単行本
- この商品を含むブログを見る
第5章 アルゴリズムを改良するコツ
この章のゴールは アルゴリズムを改良するには、どこに着目すればよいか
書籍中ではバブルソートを例にとって説明している。
バブルソートについて
バブルソート
ソートのアルゴリズムの一つ。隣り合う要素の大小を比較しながら整列させること。最悪計算時間がO(n2)と遅いが、アルゴリズムが単純で実装が容易なため、また並列処理との親和性が高いことから、しばしば用いられる。安定な内部ソート。基本交換法、隣接交換法ともいう。(単に交換法と言う場合もある)
バブルソート - Wikipedia
この動画を見るとどういう処理か分かりやすい。
要は背比べを順番にやっていくだけのソート。
全要素について確認を行っていくため最良計算時間はO(n)、平均計算時間はO(n2)。
平均計算時間がO(n2)なので、以下にもある通り、値の比較をn-1回を続けるため。
イメージは以下となる。
実装
def bubble_sort(array): n = len(array) for i in range(0, n-1): print("{}回目処理".format(str(i+1))) for j in range(0, n-1): print("処理対象{}・比較対象{}".format(array[j],array[j+1])) if array[j+1] < array[j]: array[j+1], array[j] = array[j], array[j+1] print(array) print("{}回目処理終了".format(str(i+1))) print() array = [1,2,3,4,5,3,2,1,7,0] print("処理前:", array) print("") bubble_sort(array) print("処理後 ", array)
処理前: [1, 2, 3, 4, 5, 3, 2, 1, 7, 0] 1回目処理 処理対象1・比較対象2 [1, 2, 3, 4, 5, 3, 2, 1, 7, 0] 処理対象2・比較対象3 [1, 2, 3, 4, 5, 3, 2, 1, 7, 0] 処理対象3・比較対象4 [1, 2, 3, 4, 5, 3, 2, 1, 7, 0] 処理対象4・比較対象5 [1, 2, 3, 4, 5, 3, 2, 1, 7, 0] 処理対象5・比較対象3 [1, 2, 3, 4, 3, 5, 2, 1, 7, 0] 処理対象5・比較対象2 [1, 2, 3, 4, 3, 2, 5, 1, 7, 0] 処理対象5・比較対象1 [1, 2, 3, 4, 3, 2, 1, 5, 7, 0] 処理対象5・比較対象7 [1, 2, 3, 4, 3, 2, 1, 5, 7, 0] 処理対象7・比較対象0 [1, 2, 3, 4, 3, 2, 1, 5, 0, 7] 1回目処理終了 2回目処理 処理対象1・比較対象2 [1, 2, 3, 4, 3, 2, 1, 5, 0, 7] 処理対象2・比較対象3 [1, 2, 3, 4, 3, 2, 1, 5, 0, 7] 処理対象3・比較対象4 [1, 2, 3, 4, 3, 2, 1, 5, 0, 7] 処理対象4・比較対象3 [1, 2, 3, 3, 4, 2, 1, 5, 0, 7] 処理対象4・比較対象2 [1, 2, 3, 3, 2, 4, 1, 5, 0, 7] 処理対象4・比較対象1 [1, 2, 3, 3, 2, 1, 4, 5, 0, 7] 処理対象4・比較対象5 [1, 2, 3, 3, 2, 1, 4, 5, 0, 7] 処理対象5・比較対象0 [1, 2, 3, 3, 2, 1, 4, 0, 5, 7] 処理対象5・比較対象7 [1, 2, 3, 3, 2, 1, 4, 0, 5, 7] 2回目処理終了 3回目処理 処理対象1・比較対象2 [1, 2, 3, 3, 2, 1, 4, 0, 5, 7] 処理対象2・比較対象3 [1, 2, 3, 3, 2, 1, 4, 0, 5, 7] 処理対象3・比較対象3 [1, 2, 3, 3, 2, 1, 4, 0, 5, 7] 処理対象3・比較対象2 [1, 2, 3, 2, 3, 1, 4, 0, 5, 7] 処理対象3・比較対象1 [1, 2, 3, 2, 1, 3, 4, 0, 5, 7] 処理対象3・比較対象4 [1, 2, 3, 2, 1, 3, 4, 0, 5, 7] 処理対象4・比較対象0 [1, 2, 3, 2, 1, 3, 0, 4, 5, 7] 処理対象4・比較対象5 [1, 2, 3, 2, 1, 3, 0, 4, 5, 7] 処理対象5・比較対象7 [1, 2, 3, 2, 1, 3, 0, 4, 5, 7] 3回目処理終了 4回目処理 処理対象1・比較対象2 [1, 2, 3, 2, 1, 3, 0, 4, 5, 7] 処理対象2・比較対象3 [1, 2, 3, 2, 1, 3, 0, 4, 5, 7] 処理対象3・比較対象2 [1, 2, 2, 3, 1, 3, 0, 4, 5, 7] 処理対象3・比較対象1 [1, 2, 2, 1, 3, 3, 0, 4, 5, 7] 処理対象3・比較対象3 [1, 2, 2, 1, 3, 3, 0, 4, 5, 7] 処理対象3・比較対象0 [1, 2, 2, 1, 3, 0, 3, 4, 5, 7] 処理対象3・比較対象4 [1, 2, 2, 1, 3, 0, 3, 4, 5, 7] 処理対象4・比較対象5 [1, 2, 2, 1, 3, 0, 3, 4, 5, 7] 処理対象5・比較対象7 [1, 2, 2, 1, 3, 0, 3, 4, 5, 7] 4回目処理終了 5回目処理 処理対象1・比較対象2 [1, 2, 2, 1, 3, 0, 3, 4, 5, 7] 処理対象2・比較対象2 [1, 2, 2, 1, 3, 0, 3, 4, 5, 7] 処理対象2・比較対象1 [1, 2, 1, 2, 3, 0, 3, 4, 5, 7] 処理対象2・比較対象3 [1, 2, 1, 2, 3, 0, 3, 4, 5, 7] 処理対象3・比較対象0 [1, 2, 1, 2, 0, 3, 3, 4, 5, 7] 処理対象3・比較対象3 [1, 2, 1, 2, 0, 3, 3, 4, 5, 7] 処理対象3・比較対象4 [1, 2, 1, 2, 0, 3, 3, 4, 5, 7] 処理対象4・比較対象5 [1, 2, 1, 2, 0, 3, 3, 4, 5, 7] 処理対象5・比較対象7 [1, 2, 1, 2, 0, 3, 3, 4, 5, 7] 5回目処理終了 6回目処理 処理対象1・比較対象2 [1, 2, 1, 2, 0, 3, 3, 4, 5, 7] 処理対象2・比較対象1 [1, 1, 2, 2, 0, 3, 3, 4, 5, 7] 処理対象2・比較対象2 [1, 1, 2, 2, 0, 3, 3, 4, 5, 7] 処理対象2・比較対象0 [1, 1, 2, 0, 2, 3, 3, 4, 5, 7] 処理対象2・比較対象3 [1, 1, 2, 0, 2, 3, 3, 4, 5, 7] 処理対象3・比較対象3 [1, 1, 2, 0, 2, 3, 3, 4, 5, 7] 処理対象3・比較対象4 [1, 1, 2, 0, 2, 3, 3, 4, 5, 7] 処理対象4・比較対象5 [1, 1, 2, 0, 2, 3, 3, 4, 5, 7] 処理対象5・比較対象7 [1, 1, 2, 0, 2, 3, 3, 4, 5, 7] 6回目処理終了 7回目処理 処理対象1・比較対象1 [1, 1, 2, 0, 2, 3, 3, 4, 5, 7] 処理対象1・比較対象2 [1, 1, 2, 0, 2, 3, 3, 4, 5, 7] 処理対象2・比較対象0 [1, 1, 0, 2, 2, 3, 3, 4, 5, 7] 処理対象2・比較対象2 [1, 1, 0, 2, 2, 3, 3, 4, 5, 7] 処理対象2・比較対象3 [1, 1, 0, 2, 2, 3, 3, 4, 5, 7] 処理対象3・比較対象3 [1, 1, 0, 2, 2, 3, 3, 4, 5, 7] 処理対象3・比較対象4 [1, 1, 0, 2, 2, 3, 3, 4, 5, 7] 処理対象4・比較対象5 [1, 1, 0, 2, 2, 3, 3, 4, 5, 7] 処理対象5・比較対象7 [1, 1, 0, 2, 2, 3, 3, 4, 5, 7] 7回目処理終了 8回目処理 処理対象1・比較対象1 [1, 1, 0, 2, 2, 3, 3, 4, 5, 7] 処理対象1・比較対象0 [1, 0, 1, 2, 2, 3, 3, 4, 5, 7] 処理対象1・比較対象2 [1, 0, 1, 2, 2, 3, 3, 4, 5, 7] 処理対象2・比較対象2 [1, 0, 1, 2, 2, 3, 3, 4, 5, 7] 処理対象2・比較対象3 [1, 0, 1, 2, 2, 3, 3, 4, 5, 7] 処理対象3・比較対象3 [1, 0, 1, 2, 2, 3, 3, 4, 5, 7] 処理対象3・比較対象4 [1, 0, 1, 2, 2, 3, 3, 4, 5, 7] 処理対象4・比較対象5 [1, 0, 1, 2, 2, 3, 3, 4, 5, 7] 処理対象5・比較対象7 [1, 0, 1, 2, 2, 3, 3, 4, 5, 7] 8回目処理終了 9回目処理 処理対象1・比較対象0 [0, 1, 1, 2, 2, 3, 3, 4, 5, 7] 処理対象1・比較対象1 [0, 1, 1, 2, 2, 3, 3, 4, 5, 7] 処理対象1・比較対象2 [0, 1, 1, 2, 2, 3, 3, 4, 5, 7] 処理対象2・比較対象2 [0, 1, 1, 2, 2, 3, 3, 4, 5, 7] 処理対象2・比較対象3 [0, 1, 1, 2, 2, 3, 3, 4, 5, 7] 処理対象3・比較対象3 [0, 1, 1, 2, 2, 3, 3, 4, 5, 7] 処理対象3・比較対象4 [0, 1, 1, 2, 2, 3, 3, 4, 5, 7] 処理対象4・比較対象5 [0, 1, 1, 2, 2, 3, 3, 4, 5, 7] 処理対象5・比較対象7 [0, 1, 1, 2, 2, 3, 3, 4, 5, 7] 9回目処理終了 処理後 [0, 1, 1, 2, 2, 3, 3, 4, 5, 7]
アルゴリズムを改良する
実装したバブルソートは、すでに確定してしまっている桁数に対してももう一度交換してしまっている。
これは無駄な処理なので、確定済については処理しないように実装する。
def bubble_sort(array): n = len(array) end_exchenge=n for i in range(0, n-1): print("{}回目処理".format(str(i+1))) for j in range(0, n-1): # すでに確定してしまった処理はスキップする if end_exchenge == j: break; print("処理対象{}・比較対象{}".format(array[j],array[j+1])) if array[j+1] < array[j]: array[j+1], array[j] = array[j], array[j+1] print(array) end_exchenge -= 1 print("{}回目処理終了".format(str(i+1))) print() array = [1,2,3,4,5,3,2,1,7,0] print("処理前:", array) print("") bubble_sort(array) print("処理後 ", array)
処理前: [1, 2, 3, 4, 5, 3, 2, 1, 7, 0] 1回目処理 処理対象1・比較対象2 [1, 2, 3, 4, 5, 3, 2, 1, 7, 0] 処理対象2・比較対象3 [1, 2, 3, 4, 5, 3, 2, 1, 7, 0] 処理対象3・比較対象4 [1, 2, 3, 4, 5, 3, 2, 1, 7, 0] 処理対象4・比較対象5 [1, 2, 3, 4, 5, 3, 2, 1, 7, 0] 処理対象5・比較対象3 [1, 2, 3, 4, 3, 5, 2, 1, 7, 0] 処理対象5・比較対象2 [1, 2, 3, 4, 3, 2, 5, 1, 7, 0] 処理対象5・比較対象1 [1, 2, 3, 4, 3, 2, 1, 5, 7, 0] 処理対象5・比較対象7 [1, 2, 3, 4, 3, 2, 1, 5, 7, 0] 処理対象7・比較対象0 [1, 2, 3, 4, 3, 2, 1, 5, 0, 7] 1回目処理終了 2回目処理 処理対象1・比較対象2 [1, 2, 3, 4, 3, 2, 1, 5, 0, 7] 処理対象2・比較対象3 [1, 2, 3, 4, 3, 2, 1, 5, 0, 7] 処理対象3・比較対象4 [1, 2, 3, 4, 3, 2, 1, 5, 0, 7] 処理対象4・比較対象3 [1, 2, 3, 3, 4, 2, 1, 5, 0, 7] 処理対象4・比較対象2 [1, 2, 3, 3, 2, 4, 1, 5, 0, 7] 処理対象4・比較対象1 [1, 2, 3, 3, 2, 1, 4, 5, 0, 7] 処理対象4・比較対象5 [1, 2, 3, 3, 2, 1, 4, 5, 0, 7] 処理対象5・比較対象0 [1, 2, 3, 3, 2, 1, 4, 0, 5, 7] 処理対象5・比較対象7 [1, 2, 3, 3, 2, 1, 4, 0, 5, 7] 2回目処理終了 3回目処理 処理対象1・比較対象2 [1, 2, 3, 3, 2, 1, 4, 0, 5, 7] 処理対象2・比較対象3 [1, 2, 3, 3, 2, 1, 4, 0, 5, 7] 処理対象3・比較対象3 [1, 2, 3, 3, 2, 1, 4, 0, 5, 7] 処理対象3・比較対象2 [1, 2, 3, 2, 3, 1, 4, 0, 5, 7] 処理対象3・比較対象1 [1, 2, 3, 2, 1, 3, 4, 0, 5, 7] 処理対象3・比較対象4 [1, 2, 3, 2, 1, 3, 4, 0, 5, 7] 処理対象4・比較対象0 [1, 2, 3, 2, 1, 3, 0, 4, 5, 7] 処理対象4・比較対象5 [1, 2, 3, 2, 1, 3, 0, 4, 5, 7] 3回目処理終了 4回目処理 処理対象1・比較対象2 [1, 2, 3, 2, 1, 3, 0, 4, 5, 7] 処理対象2・比較対象3 [1, 2, 3, 2, 1, 3, 0, 4, 5, 7] 処理対象3・比較対象2 [1, 2, 2, 3, 1, 3, 0, 4, 5, 7] 処理対象3・比較対象1 [1, 2, 2, 1, 3, 3, 0, 4, 5, 7] 処理対象3・比較対象3 [1, 2, 2, 1, 3, 3, 0, 4, 5, 7] 処理対象3・比較対象0 [1, 2, 2, 1, 3, 0, 3, 4, 5, 7] 処理対象3・比較対象4 [1, 2, 2, 1, 3, 0, 3, 4, 5, 7] 4回目処理終了 5回目処理 処理対象1・比較対象2 [1, 2, 2, 1, 3, 0, 3, 4, 5, 7] 処理対象2・比較対象2 [1, 2, 2, 1, 3, 0, 3, 4, 5, 7] 処理対象2・比較対象1 [1, 2, 1, 2, 3, 0, 3, 4, 5, 7] 処理対象2・比較対象3 [1, 2, 1, 2, 3, 0, 3, 4, 5, 7] 処理対象3・比較対象0 [1, 2, 1, 2, 0, 3, 3, 4, 5, 7] 処理対象3・比較対象3 [1, 2, 1, 2, 0, 3, 3, 4, 5, 7] 5回目処理終了 6回目処理 処理対象1・比較対象2 [1, 2, 1, 2, 0, 3, 3, 4, 5, 7] 処理対象2・比較対象1 [1, 1, 2, 2, 0, 3, 3, 4, 5, 7] 処理対象2・比較対象2 [1, 1, 2, 2, 0, 3, 3, 4, 5, 7] 処理対象2・比較対象0 [1, 1, 2, 0, 2, 3, 3, 4, 5, 7] 処理対象2・比較対象3 [1, 1, 2, 0, 2, 3, 3, 4, 5, 7] 6回目処理終了 7回目処理 処理対象1・比較対象1 [1, 1, 2, 0, 2, 3, 3, 4, 5, 7] 処理対象1・比較対象2 [1, 1, 2, 0, 2, 3, 3, 4, 5, 7] 処理対象2・比較対象0 [1, 1, 0, 2, 2, 3, 3, 4, 5, 7] 処理対象2・比較対象2 [1, 1, 0, 2, 2, 3, 3, 4, 5, 7] 7回目処理終了 8回目処理 処理対象1・比較対象1 [1, 1, 0, 2, 2, 3, 3, 4, 5, 7] 処理対象1・比較対象0 [1, 0, 1, 2, 2, 3, 3, 4, 5, 7] 処理対象1・比較対象2 [1, 0, 1, 2, 2, 3, 3, 4, 5, 7] 8回目処理終了 9回目処理 処理対象1・比較対象0 [0, 1, 1, 2, 2, 3, 3, 4, 5, 7] 処理対象1・比較対象1 [0, 1, 1, 2, 2, 3, 3, 4, 5, 7] 9回目処理終了 処理後 [0, 1, 1, 2, 2, 3, 3, 4, 5, 7]