#Pythonで学ぶアルゴリズム< バブルソート >
##はじめに
基本的なアルゴリズムをPythonで実装し，アルゴリズムの理解を深める．
その第17弾として挿入ソートを扱う．
##バブルソート
一般に交換ソートいうとバブルソートを指す．
リストの隣り合ったデータを比較して，大小の順序が違っているときは並べていく．そのイメージ図を次に示す．
##実装
先ほどの手順に従ったプログラムのコードとそのときの出力を以下に示す．
#####コード
"""
2021/01/10
@Yuya Shimizu
バブルソート
"""
def bubble_sort(data):
"""バブルソート：前から2つずつデータを比較し並べ替える．"""
for i in range(len(data)):
for j in range(len(data) - i -1):
if data[j] > data[j+1]: #左の方が大きい場合
data[j], data[j+1] = data[j+1], data[j] #前後入れ替え
return data
if __name__ == '__main__':
DATA = [6, 15, 4, 2, 8, 5, 11, 9, 7, 13]
sorted_data = bubble_sort(DATA.copy())
print(f"{DATA} → {sorted_data}")
#####出力
[6, 15, 4, 2, 8, 5, 11, 9, 7, 13] → [2, 4, 5, 6, 7, 8, 9, 11, 13, 15]
うまく入れ替えられているが，これでは比較入れ替えが途中で必要なくなったとしてもデータの数だけ必ず繰り返すことになる．その部分を省くために，一巡して入れ替えが行われなくなった場合，繰り返しを抜ける操作を付け加えた．そのコードと出力を以下に示す．
#####コード
"""
2021/01/10
@Yuya Shimizu
バブルソート（改良版）
"""
def bubble_sort(data):
"""バブルソート：前から2つずつデータを比較し並べ替える．ただし，交換がもう必要ない所は省略する"""
change = True #交換の余地ありと仮定
for i in range(len(data)):
if not change: #交換の余地無しで繰り返し脱出
break
change = False #交換の余地無しと仮定
for j in range(len(data) - i -1):
if data[j] > data[j+1]: #左の方が大きい場合
data[j], data[j+1] = data[j+1], data[j] #前後入れ替え
change = True #交換の余地ありかも
return data
if __name__ == '__main__':
DATA = [6, 15, 4, 2, 8, 5, 11, 9, 7, 13]
sorted_data = bubble_sort(DATA.copy())
print(f"{DATA} → {sorted_data}")
#####出力
[6, 15, 4, 2, 8, 5, 11, 9, 7, 13] → [2, 4, 5, 6, 7, 8, 9, 11, 13, 15]
ちゃんと昇順に並べ替えられていることが分かる．
今回は並べ替える前後での比較をしたいがために，あえてsorted_dataという変数に結果を格納し，さらに関数への引数はDATA.copy()というようにcopy関数により，引数に影響が出ないようにしている．並べ替えるだけなら，そのような操作は必要でなく，bubble_sort(DATA)とすればよい．
##バブルソートの計算量
最後に計算量について触れる．
基本的に選択ソートと同様，**計算量はオーダー記法で表すと，$O(n^2)$となる．
ただし，一度も交換が発生しない場合は，比較のみ（入れ替えなし）で済むため$O(n)$**となる．
最悪時間計算量が$O(n^2)$であることに変わりはない．
##感想
前回に引き続き，そこまで複雑ではなかった．リスト内で一度に入れ替えを行うとき，一時的に値を保存する必要はなく，次のようにカンマで代入するだけでよいことを知った．これは大きなものを得られたと思う．
data[j+1], data[j] = data[j], data[j+1]
次回以降の並べ替えアルゴリズムも楽しみである．
##参考文献
Pythonで始めるアルゴリズム入門 伝統的なアルゴリズムで学ぶ定石と計算量
増井 敏克 著 翔泳社