バブルソートの説明
バブルソートは、データをソートするための単純なアルゴリズムの一つです。このアルゴリズムは、隣接する要素を比較して、逆順の場合は交換することを繰り返します。外側のループは、リスト全体がソートされるまでこれを繰り返します。
バブルソートの仕組み
まず、リスト内の最初の要素と次の要素を比較します。もし前の要素が後の要素より大きければ、これらを交換します。このプロセスをリストの最後まで繰り返し、リストの末尾には最も大きな要素が「浮かび上がる」ことから、バブルソートと呼ばれています。
バブルソートの時間計算量
バブルソートの平均および最悪の時間計算量はO(n^2)です。これは、要素数が増えると処理時間が急激に増加することを意味します。そのため、バブルソートは一般的には教育目的や小規模データに使用されます。
バブルソートの実装例
function bubbleSort(arr) {
let n = arr.length;
for (let i = 0; i < n - 1; i++) {
for (let j = 0; j < n - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
// 要素を交換
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
}
}
}
return arr;
}バブルソートの利点と欠点
- 利点: 簡単に理解でき、実装が容易です。
- 欠点: 大規模データセットでは非常に非効率的です。
参考リンク
