バブルソートとは？シンプルで効果的なソートアルゴリズムを図解で解説

アルゴリズム

2024.07.02

バブルソートとは
1. アルゴリズムの概要
性能
1. 時間計算量
2. 空間計算量
特徴
1. 長所
2. 短所
実装(Python)
参考文献

バブルソートとは

バブルソートとは、

数列を昇順に並び替えるアルゴリズムの1つ

です。

バブルソートは、隣接する要素を比較し、必要に応じて交換を繰り返すシンプルなソートアルゴリズムです。

その動作が、液体の中で大きな泡が上に浮かび上がるように見えることから、この名前が付けられました。

アルゴリズムの概要

リストの末尾から隣接する要素を比較して適切に交換し、最終的にリストの先頭にソート済みの部分が作成されていきます。

挿入ソートのアルゴリズム

- ステップ1
  
  リストの末尾から順に隣接する要素を比較する
  
  左の要素が右の要素より大きい場合、それらを交換する
- ステップ2
  
  ステップ1をリストの先頭まで行う
  
  最も小さい要素が先頭に位置することになる
- ステップ3
  
  未ソートの部分がなくなるまでステップ2を繰り返す

性能

時間計算量

時間計算量は以下の通りです。

時間計算量

平均時間計算量: \(O(N^2)\)
最良の場合（ほぼソート済み）: \(O(N)\)
最悪の場合（逆順）: \(O(N^2)\)

空間計算量

空間計算量は、 \(O(1)\)（インプレース実装可能）

特徴

長所

実装が簡単
安定ソート（同じ値の要素の相対的な順序が保たれる）
ほぼソート済みのデータに対して非常に効率的

短所

大きなデータセットに対しては非効率(O(n^2)のため)

実装(Python)

def bubble_sort(nums):
    unsorted_head = 0
    swapped = True
    while swapped:
        swapped = False
        for i in range(len(nums) - 1, unsorted_head, -1):
            if nums[i] < nums[i - 1]:
                nums[i], nums[i - 1] = nums[i - 1], nums[i]
                swapped = True
        unsorted_head += 1
        

nums = [4,2,3,1]
bubble_sort(nums)
print(nums)