バブルソート

コンピューターサイエンス理論 / 全 5 枚

コンピューターサイエンス理論 - バブルソート

隣どうしを入れ替え続ける

隣り合う2つを比べて、順番が逆なら入れ替える。これを繰り返すだけで配列は並びます。大きい値が泡のように右端へ浮いていくのでバブルソートと呼ばれます。

比較の回数と交換の回数は別物です。図解では 2 つを分けて数えます。

2重ループです。ここまでで見た O(n²) の形が、そのまま出てきました。

for (let i = 0; i < n - 1; i++) {
  for (let j = 0; j < n - 1 - i; j++) {
    if (arr[j] > arr[j + 1]) swap(arr, j, j + 1);
  }
}

1 / 5

← → キーでも送れます