【基本情報の実務】バブルソートを言葉で説明する──「なぜ整うのか」は1周で何が確定するか
開発現場の見習いから、バブルソートの説明について相談が届く。
「数値の並びを小さい順に整えるバブルソートという手順を教わったのですが、動きがピンときません。隣り合う数を比べて入れ替える…らしいのですが、なぜそれで整うのでしょうか。図が描けなくてもいいので、言葉で流れを説明してもらえますか？」
相談の中に、答えるべきところがはっきり書かれている。「なぜそれで整うのでしょうか」である。基本情報の知識がここで力になるのは、手順をもう一度なぞる説明を、しないと決めたときだ。手順は、もう聞いている。この記事では、そこから整理する。
まず結論：1周ごとに、端が1つ確定する
| 言えること | |
|---|---|
| 1周終わったとき | いちばん大きい数が、右端に来ている |
| 2周終わったとき | 大きいほうから2つが、右に並んでいる |
| 3周終わったとき | 大きいほうから3つが、右に並んでいる |
これが「なぜ整うのか」への答えである。
1周するたびに、確定するものが1つ増える。増え続けるので、いつか全部が確定する。
この一言を先に渡すと、そのあとの手順が、すべて「そのための動き」として読める。
逆に、これを渡さずに手順だけを説明すると「比べて入れ替える」を何度も見ることになる。見ているものは正しいのに、意味が付かない。
手順を追う説明が、効かない理由
説明を頼まれると順を追って書きたくなる。「まず1番目と2番目を比べて、大きいほうを右へ。次に2番目と3番目を比べて……」
これは正確である。それでも「なぜ整うのか」には答えていない。
理由は一手ずつ見ているあいだ、全体が見えないことである。目の前の2つしか出てこない。
相談者はその一手は分かっている。分からないのは、それを繰り返すと、なぜ並ぶのかのほうである。
だから説明では一手ではなく、1周を単位にする。
1周してみて、何が言えるようになったか——ここに答えがある。
これは他の手順を説明するときにも使える。「1回終わると、何が確定するか」を探す。そこが見つかれば、繰り返す理由が説明できる。
例は、小さくする
言葉だけで説明するなら数は4つでよい。
5、3、8、1で1周してみる。小さい順に並べたいので、比べて、左のほうが大きければ入れ替える。
- 5と3を比べる。5のほうが大きいので入れ替える → 3、5、8、1
- 5と8を比べる。5のほうが小さいので、そのまま → 3、5、8、1
- 8と1を比べる。8のほうが大きいので入れ替える → 3、5、1、8
1周終わった。まだ整っていない（3、5、1、8）。
それでも8が右端に来ている。そして、もう動かない。
ここが説明の山場である。なぜ8が右端に来るかというと、8はどれと比べても勝つので、当たった時点から右へ運ばれ続けたからである。
いちばん大きい数は、必ず右端まで運ばれる。途中で止まる理由が無い。
だから1周すれば、いちばん大きい数は確定する。これが毎周起きる。
ついでに分かること
この見方をすると2つのことが、おまけで説明できる。
①比べる回数が、周ごとに減らせる
右端は確定しているので次の周では、そこを見なくてよい。周を重ねるほど、見る範囲が狭くなる。
これを知らずに書くと、確定した部分も毎回比べることになる。結果は同じだが、無駄が残る。
②1周で1回も入れ替えが起きなければ、そこで終わってよい
入れ替えが起きないということはどの隣どうしも、左のほうが小さいということである。それは、もう並んでいる状態である。
この2つは手順を丸暗記していると出てこない。「1周で何が言えるか」から考えると、自然に出てくる。
説明が理解になっているかどうかは、ここで分かる。
名前から入らない
この手順には泡の名前が付いている。軽い泡が浮かんでくる様子から来ている、と説明されることが多い。
ところが小さい順に並べるとき、実際に端へ運ばれていくのは大きい数である。
浮かぶと聞いて小さい数が動くと思うと、動きと合わなくなる。
だから名前は、理解のあとに置く。先に出すと、名前のほうに引っぱられる。
説明の順は動き → なぜ整うか → 名前でよい。名前は、覚えるための道具であって、理解の入り口ではない。
説明文の例
バブルソートが、なぜ整うのか
先に、答えから
1周するたびに、いちばん大きい数が右端に確定します。
2周目では、その次に大きい数が確定します。1周ごとに1つずつ確定が増えるので、繰り返せばいつか全部が確定します。
これが「なぜ整うのか」の答えです。以下は、この確認になります。
4つの数でやってみます
5、3、8、1を、小さい順に並べます。隣どうしを比べて、左のほうが大きければ入れ替えます。
- 5と3 → 入れ替え → 3、5、8、1
- 5と8 → そのまま → 3、5、8、1
- 8と1 → 入れ替え → 3、5、1、8
1周終わりました。まだ整っていません。それでも8が右端にいます。
なぜ8が右端に来たか
8はどの数と比べても勝つので、当たった時点から右へ運ばれ続けます。途中で止まる理由がありません。
ですのでいちばん大きい数は、1周すれば必ず右端に着きます。そして、そのあと動きません。
2周目からは
右端は確定しているので、そこを見なくて構いません。周を重ねるほど、見る範囲が狭くなります。
2周目が終わると大きいほうから2つが確定します。3周目で3つ。これを繰り返すと、全部が確定します。
終わりの見分け方
1周まわって、1回も入れ替えが起きなければ、そこで終わりです。
入れ替えが起きないということは、どの隣どうしも左のほうが小さいということで、それはもう並んでいる状態だからです。
名前について
泡が浮かぶ様子から名前が付いた、と説明されることがあります。ただ、小さい順に並べるときに端へ運ばれていくのは、大きい数のほうです。
名前は覚えるための目印として、動きが分かったあとでお使いください。
答えを先に置いた。そのあとの説明が、確認として読める。
数を4つにした。言葉だけで追えるのは、このくらいである。
1周終えて「まだ整っていません」と書いた。途中で整うと期待させない。
「途中で止まる理由がありません」——ここが説明の核である。手順の記述ではなく、理由になっている。
効率の話をおまけとして最後に置いた。先に出すと、覚えることが増える。
名前をいちばん最後にして、合わないことも書いた。
作り方の手順
- 何を聞かれているかを特定する。ここでは「なぜ整うのか」。
- 手順をなぞらない。もう聞いている。
- 1回終わると何が確定するかを探す。
- それを、いちばん先に置く。
- 例は小さくする。言葉だけなら4つ。
- 1周やってみせる。整っていないことも書く。
- なぜ確定するのかを、理由の形で書く。
- 効率の話は、おまけとして後ろに置く。
- 終わりの見分け方を書く。
- 名前は最後。理解の入り口にしない。
この場面で効いている基本情報の知識
- バブルソート——隣どうしを比べて入れ替える整列の手順
- 1周ごとの確定——最大値が端へ運ばれ、そこで動かなくなる
- 比較範囲の縮小——確定した部分は、次の周で見なくてよい
- 早期終了——入れ替えが1回も起きなければ、並んでいる
知識そのものより、「1回終わると何が確定するか」を探して、繰り返す理由を説明できることが、この場面で効いている。
説明で外したくないポイント
- 聞かれているのは「なぜ整うのか」。手順ではない。
- 一手ずつ追うと、全体が見えない。
- 1周を単位にする。何が確定したかを見る。
- 答えを先に置く。あとは確認になる。
- 例は4つ。言葉だけで追える大きさに。
- 1周では整わないことも書く。
- 「途中で止まる理由が無い」が、確定の理由。
- 比べる範囲は、周ごとに狭くなる。
- 入れ替えゼロなら、終わってよい。
- 名前は最後。動きと合わないことがある。