バブルソートアルゴリズムの解説
バブルソートとは？
バブルソートは、隣り合う要素を比較して大小を入れ替えていくことで、データを整列させるアルゴリズムです。最も小さな要素が次第にリストの前に「浮かび上がる」様子が泡に例えられ、「バブルソート」と呼ばれます。
バブルソートのステップ
- 隣り合う2つの要素を比較します。
- もし、左側の要素が右側の要素より大きければ、2つの要素を交換します。
- リストの終わりまでこの手順を繰り返します。
- リストの最後の要素は確定しているため、それ以外の部分で再び1から3の手順を繰り返します。
- 全ての要素がソートされるまで繰り返します。
バブルソートのステップごとの変化
| ステップ | リストの状態 | 交換された要素 |
|---|---|---|
| 初期状態 | [5, 2, 9, 1, 5, 6] | — |
| 1 | [2, 5, 9, 1, 5, 6] | 5, 2 |
| 2 | [2, 5, 1, 9, 5, 6] | 9, 1 |
| 3 | [2, 5, 1, 5, 9, 6] | 9, 5 |
| 4 | [2, 5, 1, 5, 6, 9] | 9, 6 |
| 5 | [2, 1, 5, 5, 6, 9] | 5, 1 |
| 6 | [1, 2, 5, 5, 6, 9] | 2, 1 |
バブルソートはどのように動いているか
バブルソートのJavaScript実装
// バブルソートのJavaScript実装
function bubbleSort(arr) {
let len = arr.length;
let swapped;
do {
swapped = false;
for (let i = 0; i < len - 1; i++) {
if (arr[i] > arr[i + 1]) {
// 要素を入れ替える
let temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
swapped = true;
console.log(arr); // 途中経過を出力
}
}
} while (swapped);
return arr;
}
let array = [5, 2, 9, 1, 5, 6];
console.log("ソート前:", array);
console.log("ソート後:", bubbleSort(array));
バブルソートのPython実装
# バブルソートのPython実装
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]
print(arr) # 途中経過を出力
return arr
array = [5, 2, 9, 1, 5, 6]
print("ソート前:", array)
print("ソート後:", bubble_sort(array))
まとめ
バブルソートは最も基本的なソートアルゴリズムの一つで、理解しやすい反面、大規模なデータには効率的ではありません。しかし、アルゴリズムの基本を学ぶには最適な例であり、実際の実装を通じてその動作を理解することが重要です。