【整列アルゴリズム講座】🐟バブルソート編🐟

The simplest sorting algo! バブルソート

始まりました。
整列アルゴリズム講座、第一弾です。

この講座では、整列アルゴリズムの特徴について簡単に紹介するとともに、より低レイヤの技術・実装について分かりやすく説明することを目的としています。

---

当講座では以下の整列アルゴリズムを紹介します。

• バブルソート
• 選択ソート
• 挿入ソート
• マージソート
• クイックソート
• ヒープソート
• カウントソート
• 基数ソート
• バケットソート
• シェルソート
• コムソート
• サイクルソート
• パンケーキソート
• ノームソート
• ストゥージソート
• ビトニックソート
• 鳩の巣ソート
• 奇偶転置ソート
• カクテルソート
• ボゴソート
• スリープソート
• ストランドソート

---

では、さっそく。
バブルソートについてです。

バブルソートは一つとなりと比べては入れ替える、という処理を繰り返していく方法です。
計算量はO(n^2)です。

これをPythonで書いてみましょう♪

def bubble_sort(lst):
    # リストの長さを取得
    n = len(lst)
    for i in range(n):
        for j in range(n - i - 1):
            # リスト内の要素を比較し、順序が逆の場合は交換する
            if lst[j] > lst[j + 1]:
                lst[j], lst[j + 1] = lst[j + 1], lst[j]
    return lst

---

ちなみに、これを可視化すると以下のようになります。
このプログラムの紹介がしたくて、、、🐙🐙🐙

シンプルでわかりやすいアルゴリズムではありますが、パフォーマンスはあまりよくない整列アルゴリズムです。

デモサイト
ソースコード

---

以上。
次回は選択ソートを紹介します。