バブルソートとは?コードやアルゴリズムを初心者向けに解説

本記事はPythonのバブルソートについて、学生エンジニアが初心者の方へ向けて優しく解説しています。ソートとは数値や文字列を昇順や降順に並べ替えることで、プログラミングを学ぶ上で非常に重要な道具です。ソートの中でも極めて重要なバブルソートを一緒に学習しましょう!

バブルソートとは?

ソートとは、
数値や文字列を昇順や降順に並べ替えることで、
バブルソートとは2つの値を比較しながら並べ替えるアルゴリズムです。

ソートの1種であるバブルソートは、隣り合う要素を比較しながら整列させます。
並列処理に強いバブルソートは、現代でもたくさんの場面で使用されます。

バブルソートは言葉で解説するよりも、
ソートの方法を動画でイメージするほうが理解につながります。
下の動画を見てください。2倍速で見ることをオススメします。


いかがでしたでしょうか。
バブルソートは直感的で理解しやすいソートです。
隣り合う値の大小を比べ合い、その比較結果によって順番に並べ替えていきます。
では、実際にPythonでバブルソートを実行してみましょう。

バブルソートの計算量

平均計算時間最悪計算時間最良計算時間
O(n2O(n2O(n)

バブルソートの計算量は「O(n2)」であり、比較回数は「 n(n-1)/2 」です。

バブルソートの問題点

下の動画もバブルソートのアルゴリズムです。
動画では右に位置する小さな値は、右へ移動するまでに非常に時間がかかっていることがわかります。
この点が、バブルソートの欠点です。


Pythonコード

def bubble_sort(num):
    for i in range(len(num)):
        for j in range(len(num) - 1 - i):
            if num[j] > num[j + 1]:
                num[j], num[j + 1] = num[j + 1], num[j]
return num

上記がPythonを用いて作成したバブルソートの関数です。
バブルソートは、どのサイトや本を見ても同じようなコードになっています。
動画でイメージしたソートを意識しながら、自力でコードが組めるように手を動かしてみてください。非常に理解が深まるかと思います。

特に3行目で理解に苦しむ方が多いと思います。
後半の値が決定されてゆくにつれて、
比較する値が減少することを「len(num) – 1 – i」このコードで可能にしているだけで、極めて簡単です。
ゆっくり理解してみてください。

Pythonでバブルソートを記述するにあたって、
バブルソートは2重ループで隣接の値を比較する
これを覚えておけば、バッチリです。

バブルソートの実行

上記で作成した関数を使用して、実際にバブルソートをPython環境で実行してみました。
下記がそのコードと実行結果です。

def bubble_sort(num):
    for i in range(len(num)):
        for j in range(len(num) - 1 - i):
            if num[j] > num[j + 1]:
                num[j], num[j + 1] = num[j + 1], num[j]
    return num

if __name__ == '__main__':
    import random
    num = [10, 8, 2, 5, 7, 9]
    print(bubble_sort(num))
【実行結果】
[2, 5, 7, 8, 9, 10]

実行結果から、
10行目で宣言した [10, 8, 2, 5, 7, 9]のリストを昇順に上手くソートできていることがわかります。

ということで、本記事はバブルソートについてまとめました。
最後まで読んでいただき、ありがろうございました\(^o^)/

オススメのPC機器

【トラックボールマウス】
トラックボール付きマウスは、作業効率が爆上がりします。
レビューを見ていただければわかりますが、間違いなく損のない買い物になります\(^o^)/

【PC外部モニター】
外部モニターがあるだけで、PC作業がぐっと楽になります。
僕も使ってているASUSのコスパ最強モニターが1番のおすすめです\(^o^)/

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です