バブルソート（Bubble Sort）

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

1. 基本的な仕組み
2. 図による説明
3. バブルソートのシミュレーション
4. 実装例（JavaScript）
5. バブルソートの特徴
6. その他のソート

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. バブルソートのシミュレーション

4. 実装例（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]));