🗂

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

2023/01/08に公開約1,100字

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

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

bubble_sort

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

デモサイト
ソースコード


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

Discussion

ログインするとコメントできます