バブルソートアルゴリズム

🎯 学習目標

バブルソートの仕組みを理解する
隣接要素の比較と交換の流れを把握する
アルゴリズムの効率性について考える

バブルソートとは

バブルソートは、隣り合う2つの要素を比較して、順序が逆であれば交換する操作を繰り返すソートアルゴリズムです。

名前の由来：大きな値が「泡（バブル）」のように配列の後ろに浮き上がっていく様子から。

アルゴリズムの流れ

隣接要素の比較：配列の先頭から隣り合う2つの要素を比較
条件による交換：左の要素が右の要素より大きければ交換
次の要素へ：次の隣接ペアに移動
1回のパス完了：配列の最後まで到達
繰り返し：未ソート部分がなくなるまで1-4を繰り返し

アルゴリズムの可視化

バブルソートは以下のような動作をします：

第1パス: [64, 34, 25, 12, 22, 11, 90] → [34, 25, 12, 22, 11, 64, 90]
第2パス: [34, 25, 12, 22, 11, 64, 90] → [25, 12, 22, 11, 34, 64, 90]
第3パス: [25, 12, 22, 11, 34, 64, 90] → [12, 22, 11, 25, 34, 64, 90]
第4パス: [12, 22, 11, 25, 34, 64, 90] → [12, 11, 22, 25, 34, 64, 90]
第5パス: [12, 11, 22, 25, 34, 64, 90] → [11, 12, 22, 25, 34, 64, 90]

各パスで最大値が右端に「浮き上がって」いきます。

JavaScriptでの実装

function bubbleSort(arr) {
    // 配列をコピー（元の配列を変更しないため）
    let sortedArray = [...arr];
    let n = sortedArray.length;
    
    console.log("初期配列:", sortedArray);
    
    // 外側のループ：パス数を制御
    for (let i = 0; i < n - 1; i++) {
        console.log(`\n--- パス ${i + 1} 開始 ---`);
        let swapped = false; // 交換が発生したかのフラグ
        
        // 内側のループ：隣接要素の比較
        for (let j = 0; j < n - i - 1; j++) {
            console.log(`比較: ${sortedArray[j]} と ${sortedArray[j + 1]}`);
            
            // 左の要素が右の要素より大きい場合は交換
            if (sortedArray[j] > sortedArray[j + 1]) {
                // 交換処理
                let temp = sortedArray[j];
                sortedArray[j] = sortedArray[j + 1];
                sortedArray[j + 1] = temp;
                swapped = true;
                
                console.log(`交換後: [${sortedArray.join(', ')}]`);
            }
        }
        
        console.log(`パス ${i + 1} 終了: [${sortedArray.join(', ')}]`);
        
        // もし交換が1回も発生しなかった場合、ソート完了
        if (!swapped) {
            console.log("早期終了：ソート完了");
            break;
        }
    }
    
    console.log("\\n最終結果:", sortedArray);
    return sortedArray;
}

// テスト実行
let testArray = [64, 34, 25, 12, 22, 11, 90];
bubbleSort(testArray);

時間計算量の分析

最悪の場合：O(n²)

配列が逆順にソートされている場合
すべての要素をすべての要素と比較する必要がある
比較回数：n × (n-1) / 2

最良の場合：O(n)

配列が既にソートされている場合
1回のパスで完了（改良版の場合）

平均的な場合：O(n²)

💡 特徴とポイント

長所

理解しやすい：アルゴリズムが直感的
実装が簡単：少ないコードで実装可能
安定ソート：同じ値の要素の順序が保たれる
その場ソート：追加メモリをほとんど使わない

短所

効率が悪い：大きなデータに対して非常に遅い
比較回数が多い：常にO(n²)の比較が必要

実際の使用場面

バブルソートは教育目的以外ではほとんど使用されません。

実用的なソートアルゴリズム：

クイックソート：平均O(n log n)
マージソート：常にO(n log n)
ヒープソート：常にO(n log n)

次のステップ

次のスライドでは、より効率的な選択ソートについて学習します！

推定学習時間: 10分