【解説】 バブルソート
アルゴリズムの仕組み
基本的な動きは、**「リストの端から隣同士を比較し、大きい方を後ろへ送る」**の繰り返しです。
-
リストの先頭から順に、隣り合う2つの要素を比較します。
-
左の要素が右の要素より大きい場合、その2つを入れ替えます（昇順の場合）。
-
これをリストの最後まで繰り返すと、一番大きな要素が最後に配置されます。
-
最後の要素を除いた残りの部分で、再び同じ操作を繰り返します。
-
入れ替えが発生しなくなるか、すべての要素が確定するまで続けます。
特徴と性能
バブルソートは教育用としては優れていますが、大量のデータを扱う実用的な場面ではあまり使われません。
-
時間計算量:
-
平均・最悪の場合：O(n^2)
-
（要素数が2倍になると、計算時間は4倍かかります）
-
-
空間計算量: O(1)
-
追加のメモリをほとんど使わないため、省スペースです。
-
-
安定性: 安定なソート
-
同じ値の要素が複数ある場合、その前後関係は維持されます。
-
# バブルソート
def bubble_sort(arr):
n = len(arr)
# 全体のパスを繰り返す
for i in range:
# 最後の i 個はすでに確定しているので無視する
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
# 使用例
data = [64, 34, 25, 12, 22, 11, 90]
sorted_data = bubble_sort(data)
print(f"ソート後: {sorted_data}")