概要
概要
左から隣接要素を比べ、逆順なら交換します。1 パス終わるごとに未確定部分の最大値が右端へ確定します。
ソート / Bubble Sort（バブルソート）
左から隣接要素を比べ、逆順なら交換します。1 パス終わるごとに未確定部分の最大値が右端へ確定します。
目次
このページでわかること
概要
左から隣接要素を比べ、逆順なら交換します。1 パス終わるごとに未確定部分の最大値が右端へ確定します。
考え方
for i = 0 to n - 2
for j = 0 to n - 2 - i
if a[j] > a[j + 1]
swap a[j], a[j + 1]
mark last unsorted item as sorted要点
O(n) / 交換がなければ早く終わる
O(n²)
O(n²)
はい
補足
ほぼ毎パスで未整列部分をなめるので、比較回数が二次的に増えます。
比較、交換、確定という基本概念がそのまま見えるからです。
最大値が泡のように右へ浮いていく感覚を掴むと定着します。
動きで確認
ここでは「比較中の 2 本を見る」を見ながら、上で読んだ内容を動きと結びつけます。
次に見る
比較すると違いがわかりやすいページを先に置いています。