バブルソート

バブルソートは最も基本的なソートアルゴリズムの一つです。隣り合う要素を比較し、必要に応じて交換を繰り返すことで配列を整列させる手法です。

1. 基本的な仕組み

配列の先頭から順に、隣り合う2つの要素を比較します
順序が間違っている場合（例：昇順ソートなら左の要素が右の要素より大きい場合）、2つの要素を交換します
配列の末尾まで到達したら、再び先頭に戻り同じ処理を繰り返します
一度の走査で交換が発生しなければ、配列は整列完了です

2. 図による説明

以下にバブルソートの実行過程を視覚的に示します。

配列 [5, 3, 8, 4, 2] を昇順にソートする過程を見てみましょう。

第1走査

[5, 3, 8, 4, 2] → 5と3を比較 → 5>3なので交換 → [3, 5, 8, 4, 2]
[3, 5, 8, 4, 2] → 5と8を比較 → 5<8なので交換なし → [3, 5, 8, 4, 2]
[3, 5, 8, 4, 2] → 8と4を比較 → 8>4なので交換 → [3, 5, 4, 8, 2]
[3, 5, 4, 8, 2] → 8と2を比較 → 8>2なので交換 → [3, 5, 4, 2, 8]

この時点で最大値の8が配列の最後に位置しました。

第2走査

[3, 5, 4, 2, 8] → 3と5を比較 → 3<5なので交換なし → [3, 5, 4, 2, 8]
[3, 5, 4, 2, 8] → 5と4を比較 → 5>4なので交換 → [3, 4, 5, 2, 8]
[3, 4, 5, 2, 8] → 5と2を比較 → 5>2なので交換 → [3, 4, 2, 5, 8]

この時点で2番目に大きい値の5が正しい位置に来ました。

第3走査

[3, 4, 2, 5, 8] → 3と4を比較 → 3<4なので交換なし → [3, 4, 2, 5, 8]
[3, 4, 2, 5, 8] → 4と2を比較 → 4>2なので交換 → [3, 2, 4, 5, 8]

第4走査

[3, 2, 4, 5, 8] → 3と2を比較 → 3>2なので交換 → [2, 3, 4, 5, 8]

これで配列は完全に整列されました。

3. 実装例（JavaScript）

function bubbleSort(arr) {
  const n = arr.length;
  let swapped;
  
  for (let i = 0; i < n; i++) {
    swapped = false;
    
    // 最後のi個の要素はすでに整列済みなので、そこまでは見なくてよい
    for (let j = 0; j < n - i - 1; j++) {
      // 隣接する要素を比較
      if (arr[j] > arr[j + 1]) {
        // 要素の交換
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
        swapped = true;
      }
    }
    
    // 一度も交換が行われなければソート完了
    if (!swapped) {
      break;
    }
  }
  
  return arr;
}

// 使用例
const array = [5, 3, 8, 4, 2];
console.log("元の配列:", array);
console.log("ソート後:", bubbleSort([...array]));

4. バブルソートの特徴

4.1. 長所

実装が非常に簡単
少量のデータや、ほぼ整列されているデータに対しては効率的に動作する場合がある
インプレースソートであり、追加のメモリをほとんど必要としない

4.2. 短所

時間計算量が O(n²) であり、大きなデータセットには非効率
最悪の場合でも最良の場合でも O(n²) の処理が必要

4.3. 時間計算量

最良の場合: O(n) ※すでに整列されている場合
平均の場合: O(n²)
最悪の場合: O(n²)

4.4. 空間計算量

O(1) ※追加のメモリをほとんど使用しない

バブルソートは、教育用や小規模なデータセットの場合には適していますが、実際のアプリケーションでは効率の良いクイックソートやマージソートなどが選択されることが多いです。