pythonでソートアルゴリズム -バブルソート

はじめに

プログラミング初心者がソートアルゴリズムを自分なりに理解し、コーディングしてみたものの忘備録になります。
間違いもあるかもしれませんがご了承ください＆ご指摘いただけると助かります…。
ここでは、バブルソートを扱います。
参考にした本と記事はこちら
→https://www.codereading.com/algo_and_ds/algo/
→https://book.impress.co.jp/books/1118101057

バブルソート

基本となるソート。値の比較の様子が泡が上がっていくように見えるのでバブルソートという。
隣同士の要素を比較し、大きい値を配列の最後に押しやるイメージ。

手順

ここで青字で書いている数字(1-1, 1-2, 1-3, …)は、第1段階の1回目の比較、第2段階の2回目の比較、といった意味になる。

比較回数

比較回数は、第1段階で6回(配列の大きさ7より1少ない)、第2段階で5回、…と段階を重ねるごとに減っていくので、
配列の大きさをnとすると、

(n-1)+(n-2)+(n-3)+...+2+1 = \sum_{k=1}^{n-1} k = \frac{1}{2}n(n-1)

となる。※高校数学！！

プログラム

bubble_sort.py

a = [4,6,1,2,3,8,5]

# 段階ごとにfor文を回す
for i in range(len(a)-1):
    # 各段階の中で、順番に比較を行う
    for j in range(0, len(a)-1-i):
        if a[j] > a[j+1]:
            a[j], a[j+1] = a[j+1], a[j]

print(a)

出力結果

$ python3 bubble_sort.py
[1, 2, 3, 4, 5, 6, 8]

計算量

プログラムからわかるとおり、for文を2回まわすのでO(n^2)となる。

参考：計算量の大きさ

O(1) < O(log_2 n) < O(n) < O(n log_2 n) < O(n^2) < O(n^3) < O(2^n) < O(3^n) < O(n!)

※それぞれグラフを書いてみたらわかる！！

おわりに

初めて記事を投稿するので、練習がてら書きました。
思ったより書くのに時間がかかることがわかったので、残りのソートはサクサクと書いていきたいです。