バブルソート
バブルソート(Bubble Sort)は、簡単で理解しやすいソートアルゴリズムの一つ。隣り合う要素を比較し、大きい方を右に移動させていく操作を繰り返すことで、リストを昇順または降順に並び替える。
バブルソートの動作原理
- リストの先頭から隣り合う2つの要素を比較する
- 左側の要素の方が大きければ、2つの要素を交換する
- 1と2の操作をリストの末尾まで繰り返す
- 1回の操作が終わると、最大値が必ずリストの最後尾に移動する
- リストの長さを1つ減らして、上記の操作を繰り返す
- リストの長さが1になるまで4と5を繰り返す
Pythonによる実装
# bubble_sort.py
def bubble_sort(list):
n = len(list)
for i in range(n):
for j in range(0, n-i-1):
if list[j] > list[j+1]:
list[j], list[j+1] = list[j+1], list[j]<
return list
my_list = [64, 34, 25, 12, 22, 11, 90]
print(bubble_sort(my_list))
# [11, 12, 22, 25, 34, 64, 90]
探索の早さ
バブルソートの時間計算量は、最悪の場合 O(n^2) となる。これは、リストの長さがnの場合、最大で n*(n-1)/2 回の要素の交換が行われる可能性があるためだ。
一方、もしリストが完全に逆順にソートされている場合、最小で n*(n-1)/2 回の交換が必要となる。つまり、平均的な計算量もやはり O(n^2) となる。
このように、バブルソートは非効率的なアルゴリズムだ。しかし、ソースコードが簡単で理解しやすいため、ソートアルゴリズムの学習により適している。実用的なソートアルゴリズムとしては、計算量の優れたクイックソートやマージソートが推奨される。
