バブルソート（Bubble Sort）とは

バブルソート（Bubble Sort）は、アルゴリズムの中でも比較的単純なソート方法の一つです。要素の比較と交換を繰り返し、配列を昇順または降順に整列します。

以下に、バブルソートの手順を説明します。

  1. 配列の先頭から順番に隣接する要素を比較します。
  2. 左側の要素が右側の要素より大きい（または小さい）場合、両方の要素を交換します。
  3. 配列の最後まで比較と交換を行い、最大（または最小）の要素が配列の末尾に移動します。
  4. 末尾に移動した要素を除いて、残りの要素に対して再び 1 から 3 の手順を繰り返します。
  5. ソート済みの範囲が配列の末尾に移動していくため、比較と交換の回数が減少します。
  6. ソート済みの範囲が配列の先頭まで到達するまで繰り返し、全体の配列がソートされます。

バブルソートの特徴は、要素の交換が頻繁に行われることです。大きなデータセットに対しては効率が悪く、最悪の場合の時間計算量は O(n^2)です。しかし、実装が比較的単純で理解しやすいため、小規模なデータや部分的にソートされたデータに対しては効果的なソートアルゴリズムとして使われることもあります。

JavaScript でのバブルソートの実装例

function bubbleSort(arr) {
  var len = arr.length;
  var swapped;

  do {
    swapped = false;

    for (var i = 0; i < len - 1; i++) {
      if (arr[i] > arr[i + 1]) {
        var temp = arr[i];
        arr[i] = arr[i + 1];
        arr[i + 1] = temp;
        swapped = true;
      }
    }
  } while (swapped);

  return arr;
}

// 使用例
var array = [5, 3, 8, 4, 2];
console.log(bubbleSort(array)); // [2, 3, 4, 5, 8]

この実装では、まず swapped という変数を用意し、ループ内で要素の交換が行われたかどうかを記録します。その後、do…while ループを使って、配列を走査しながら隣接する要素を比較し、必要なら交換を行います。交換が行われた場合は swapped を true にして、再度ループを実行します。交換が行われなくなるまで繰り返すことで、配列がソートされます。

上記の例では、配列[5, 3, 8, 4, 2]をバブルソートで昇順にソートしています。結果は[2, 3, 4, 5, 8]となります。

ただし、バブルソートは効率の面ではあまり優れていないため、大きなデータセットに対しては遅くなる可能性があります。他の高速なソートアルゴリズムを使用することが推奨されます。