アルゴリズム図鑑
バブルソート
隣り合う要素を比べて、順番が逆なら入れ替える操作を繰り返す整列法です。1周するごとに、一番大きい値が右端に決まります。
考え方
- 内側のループで隣どうしを比べ、大きいほうを右へ送る
- 1周終わるたびに右端から順に値が確定するので、比べる範囲が1つずつ短くなる
- 比べる回数は n(n−1)/2 回なので、計算量は O(n²)
計算量
O(n²)
試験でのポイント
- 入れ替えには、一時的に値を逃がす変数（tmp）を使う
- 外側のループが「減らす」になっているところに注意
アルゴリズム図鑑
隣り合う要素を比べて、順番が逆なら入れ替える操作を繰り返す整列法です。1周するごとに、一番大きい値が右端に決まります。
O(n²)