バブルソートは、隣接要素の比較と交換を繰り返す基本的な比較ソートアルゴリズムです。そのシンプルさゆえに教育用途に広く用いられますが、実用性向上のためには複数の最適化戦略が存在します。

基本ロジック

各パス（ラウンド）で左から右へ隣接する2要素を比較し、左側が大きい場合に位置を入れ替えます。この操作により、最大値が配列末尾へ「浮かび上がる」ため、次回のパスでは末尾1要素を除外して処理できます。

実装例：標準版（O(n²)）

public static void basicBubbleSort(int[] arr) {
    int n = arr.length;
    for (int round = 0; round < n - 1; round++) {
        for (int idx = 0; idx < n - 1 - round; idx++) {
            if (arr[idx] > arr[idx + 1]) {
                exchange(arr, idx, idx + 1);
            }
        }
    }
}

最適化①：早期終了判定

1ラウンド内で1度も交換が発生しなければ、配列は既に昇順であると判断し、即座に処理を終了します。

public static void earlyExitBubbleSort(int[] arr) {
    int n = arr.length;
    for (int round = 0; round < n - 1; round++) {
        boolean exchanged = false;
        for (int idx = 0; idx < n - 1 - round; idx++) {
            if (arr[idx] > arr[idx + 1]) {
                exchange(arr, idx, idx + 1);
                exchanged = true;
            }
        }
        if (!exchanged) break;
    }
}

最適化②：境界動的縮小

最後に交換が行われたインデックスを記録し、次ラウンドではその位置までしか探索しないようにします。これにより、右端の既に整列済み領域を無駄にスキャンしません。

public static void adaptiveBubbleSort(int[] arr) {
    int upperBound = arr.length - 1;
    while (upperBound > 0) {
        int lastSwapIndex = 0;
        for (int idx = 0; idx < upperBound; idx++) {
            if (arr[idx] > arr[idx + 1]) {
                exchange(arr, idx, idx + 1);
                lastSwapIndex = idx;
            }
        }
        upperBound = lastSwapIndex;
    }
}

安全な要素交換メソッド

オーバーフロー回避のため、算術演算ではなく一時変数による交換を推奨します。

public static void exchange(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

注意点：不適切な最適化のリスク

境界縮小版でlastSwapIndexの初期化を忘れると、前回の値が残り、無限ループに陥る可能性があります。特に空配列や単一要素配列のテストケースで検証が必要です。