1 歩ずつ動かす
[5, 2, 8, 1, 9, 3, 7, 4] を小さい順に並べる
- 50
- 21
- 82
- 13
- 94
- 35
- 76
- 47
- 比較中
- 入れ替えた
- 位置が決まった
- いま扱う範囲
- 箱の下の数字は添字
1 歩目 / 全 45 歩比べた回数 0 回入れ替えた回数 0 回
8 個の値を小さい順に並べます。隣どうしを比べ、大きいほうを右へ運んでいきます。
いま動いている疑似コードの行
- 1i を 0 から n - 2 まで 1 つずつ増やす
- 2入れ替えたか = いいえ
- 3j を 0 から n - 2 - i まで 1 つずつ増やす
- 4a[j] > a[j + 1] なら
- 5a[j] と a[j + 1] を入れ替える (入れ替えたか = はい)
- 6右端が決まる。入れ替えなかったら、そこで終わる
見本を変える
予想してみる
いまは 1 歩目です。
次に比べる添字 0 と添字 1 は、入れ替わるでしょうか。
今回わかること
- 隣どうしを比べて入れ替え、大きい値を右へ運ぶ流れ
- 1 回の走査で右端が決まり、入れ替わらなければ早く終わる理由
前提
- 配列と添字 (0 から数える番号)
- for 文の二重の繰り返し
- 2 つの値を入れ替える書き方
どんな並べ方か
バブルソートは、左から右へ隣どうしを比べ、左のほうが大きければ入れ替える並べ方です。これを 1 回通すと、いちばん大きい値が右端に着きます。
大きい値が泡のように浮かんで右へ運ばれるのが名前の由来です。右端から 1 つずつ位置が決まるので、走査のたびに調べる範囲が 1 つ短くなります。
手順と具体例
- 1左端から、隣どうしの 2 つを比べる
- 2左のほうが大きければ、2 つを入れ替える
- 3右端まで進めたら、右端の値の位置が決まる
- 4範囲を 1 つ短くして、最初から繰り返す
- 51 回も入れ替わらなかった走査があれば、残りはもう並んでいるので終わる
| 区切り | 比べた / 入れ替えた | 終わったときの並び |
|---|---|---|
| 1 回目の走査 | 7 回 / 5 回 | 2, 5, 1, 8, 3, 7, 4, 9 |
| 2 回目の走査 | 6 回 / 4 回 | 2, 1, 5, 3, 7, 4, 8, 9 |
| 3 回目の走査 | 5 回 / 3 回 | 1, 2, 3, 5, 4, 7, 8, 9 |
| 4 回目の走査 | 4 回 / 1 回 | 1, 2, 3, 4, 5, 7, 8, 9 |
| 5 回目の走査 | 3 回 / 0 回 | 1, 2, 3, 4, 5, 7, 8, 9 |
比べる回数と計算量
| 場合 | 比べる回数 | 計算量 |
|---|---|---|
| いちばん速い | n - 1 回 (もう並んでいる) | O(n) |
| 平均 | およそ n² ÷ 2 回 | O(n²) |
| いちばん遅い | n(n - 1) ÷ 2 回 (逆順) | O(n²) |
8 個の逆順なら 28 回比べて 28 回入れ替えます。もう並んでいれば、7 回比べて 1 回も入れ替えずに終わります。
使いどころ
向いているとき
- 並べ替えの仕組みを、最初に学ぶとき
- ほとんど並んでいて、少し崩れているだけのとき
- 同じ値の順番を崩したくないとき (安定な並べ方)
向いていないとき
- 要素が数百個を超える配列 (比べる回数が n² で増える)
- 逆順に近い配列 (入れ替える回数がいちばん多くなる)
コード
疑似コード
- 1i を 0 から n - 2 まで 1 つずつ増やす
- 2入れ替えたか = いいえ
- 3j を 0 から n - 2 - i まで 1 つずつ増やす
- 4a[j] > a[j + 1] なら
- 5a[j] と a[j + 1] を入れ替える (入れ替えたか = はい)
- 6右端が決まる。入れ替えなかったら、そこで終わる
実際のコード
python実行可能
出力
▶ 実行ボタンを押すと結果がここに表示されます
Python と JavaScript は、書き換えて「実行」を押すと、その場で結果が出ます。Java は読むだけの欄です。
よくある疑問
- swapped の目印は、なぜ要るのですか？
- 1 回も入れ替わらなかった走査は、隣どうしがすべて小さい順に並んでいた印です。そこで止めれば、もう並んでいる配列を n - 1 回の比較だけで終えられます。
- a[j] > a[j + 1] を >= にすると、何が変わりますか？
- 同じ値も入れ替えるので、同じ値どうしの順番が入れ替わります。結果の並びは同じですが、安定な並べ方ではなくなり、入れ替えの回数も増えます。
- なぜ走査のたびに、調べる範囲を 1 つ短くするのですか？
- 1 回通すたびに、残った範囲でいちばん大きい値が右端へ着いて位置が決まるからです。決まった値を調べ直す必要はありません。
