小学生でもできるPythonのバブルソート実装方法をわかりやすく解説

2024年11月18日Python基礎

バブルソートとは、シンプルかつ最も基本的なソートアルゴリズムの一つです。

隣接する要素を比較し、順序が逆であれば交換することを繰り返すことで、最も大きい（または最も小さい）要素をリストの端に「バブル」させることからその名が付けられています。

アルゴリズムの手順

手順はこんな感じです。

1. リストの先頭から隣接する要素を比較する
2. 順序が逆であれば、要素を交換する
3. リストの末尾まで繰り返す
4. 先頭から繰り返して交換ができなくなったらソート完了

実装例

関数に落とし込んでみた結果はこちら。

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

arr = [2,5,3,6,8,8,3,1,5,7]
print(f"元のリスト：{arr}")
sorted_arr = bubble_sort(arr)
print(f"ソート後のリスト：{sorted_arr}")

出力結果

実際に出力した結果。

元のリスト：[2, 5, 3, 6, 8, 8, 3, 1, 5, 7]
ソート後のリスト：[1, 2, 3, 3, 5, 5, 6, 7, 8, 8]

解説

関数の中身を見ていきます。

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

まず、n = len(arr)はリストの長さです。ループに使います。

関数内の2,3行目は二重ループになっています。先ほどのリストの長さと外側のループにあて、内側のループは、すでにソートされている要素を無視するため、n-i-1としています。

if文は、対象要素の前後関係を確認して、前の方が大きい場合はj番目とj+1番目を交換するという処理です。

したがって、ループを経るごとに小さい要素が前に前に押し出されていくような流れになっています。

以上です。