JavaScriptでバブルソートを実装するコードをわかりやすく解説

今回は、数値などのリテラルからなる配列を受け取り、バブルソートを使って並べ替えるJavaScript関数を作成します。バブルソートは、隣り合う要素同士を比較し、順序が正しくなければ入れ替えるという処理を繰り返す、最も基本的なソートアルゴリズムの一つです。

バブルソートの仕組み

バブルソートでは、配列内の隣接する2つの要素を順番に比較していきます。大小関係が逆になっている場合は要素を交換し、これを配列全体に対して繰り返すことで、大きな値が徐々に末尾へ「浮かび上がる」ように移動していきます。この動きが泡（バブル）が水面に上がっていく様子に似ていることから、「バブルソート」という名前が付いています。

サンプルコード

それでは、実際のコードを見てみましょう。

const arr = [4, 56, 4, 23, 8, 4, 23, 2, 7, 8, 8, 45];

// 2つの要素を入れ替えるヘルパー関数
const swap = (items, firstIndex, secondIndex) => {
    var temp = items[firstIndex];
    items[firstIndex] = items[secondIndex];
    items[secondIndex] = temp;
};

const bubbleSort = items => {
    var len = items.length,
    i, j;
    for (i = len - 1; i >= 0; i--) {
        for (j = len - i; j >= 0; j--) {
            // 前後の要素を比較し、順序が逆なら入れ替える
            if (items[j] < items[j - 1]) {
                swap(items, j, j - 1);
            }
        }
    }
    return items;
};

console.log(bubbleSort(arr));

コードのポイントは以下の通りです。

• swap()：一時変数tempを使って、指定した2つのインデックスの要素を安全に入れ替えます。
• bubbleSort()：二重ループで配列全体を走査し、隣接する要素items[j]とitems[j - 1]を比較します。
• items[j]が前の要素よりも小さい場合はswap()を呼び出して順序を修正します。
• すべての走査が完了した時点で、配列は昇順に並べ替えられます。

出力結果

コンソールには以下のように出力されます。

[
    2,  4, 4,  4,  7,
    8,  8, 8, 23, 23,
    45, 56
]

計算量について

バブルソートの平均計算量・最悪計算量はO(n²)です。データ件数が増えると比較回数が急激に増加するため、実務ではArray.prototype.sort()やクイックソートといった効率的な手法が使われることが一般的です。しかし、ソートアルゴリズムの基礎概念を理解するための教材として、バブルソートは非常に有用な存在といえます。