バブルソート実装

並べ替えの完成形を、いきなり思い浮かべようとすると詰まる

[5, 1, 4, 2, 8] を小さい順にしてください、と言われて完成形を頭に描こうとすると手が止まります。5 個でも怪しいのに、100 個になるとまず追えません。

そこで、見る範囲をうんと狭めます。隣り合う 2 つだけを見て、左が右より大きければ入れ替える。これなら迷いようがありません。

判断材料は「左と右、どちらが大きいか」だけです。

端から順に隣を見ると、大きい値が右へ運ばれる

この「隣を見て、必要なら入れ替える」を、左端から右端まで 1 回ずつ通してみます。

• [5, 1, 4, 2, 8] — 5 と 1 を比べる。入れ替えて [1, 5, 4, 2, 8]
• 5 と 4 を比べる。入れ替えて [1, 4, 5, 2, 8]
• 5 と 2 を比べる。入れ替えて [1, 4, 2, 5, 8]
• 5 と 8 を比べる。左のほうが小さいのでそのまま

気づいてほしいのは、5 が一度も置き去りにされていないことです。入れ替えるたびに 5 が右の相棒になり、次の比較でもまた 5 が主役になる。だから 1 周すれば、その時点でいちばん大きい値が必ず右端まで運ばれます。この動きが泡の浮き上がりに似ているので、バブルソートと呼ばれます。

1 周では終わらない。ただし、次の周は 1 つ短くてよい

1 周を終えた [1, 4, 2, 5, 8] はまだ並んでいません。もう 1 周します。

• 1 と 4 はそのまま。4 と 2 を入れ替えて [1, 2, 4, 5, 8]。4 と 5 はそのまま

これで完成です。大事なのは、右端はもう確定しているという点です。1 周目で 8 の位置が決まり、2 周目で 5 の位置が決まる。周を重ねるごとに、見なければいけない範囲は右から 1 つずつ縮んでいきます。最後に残る 1 つは比べる相手がいないので、周の回数は要素数より 1 つ少なくて足ります。

比較の回数は 4 + 3 + 2 + 1 のように積み上がり、要素数の 2 乗のおよそ半分になります。100 個なら 5,000 回で気になりませんが、100,000 個だと 50 億回で、待っていられません。

もう 1 つ、周の途中の様子から分かることがあります。ある 1 周で入れ替えが一度も起きなかったなら、どの隣どうしも「左のほうが小さい」ということです。それは全体が並び終わっている証拠なので、残りの周は回さなくてかまいません。[1, 2, 3, 4, 5] を入れると、1 周目でこれが起きます。

解説

受け取った配列をそのまま並べ替えると、呼び出した側の配列まで変わってしまいます。作業用に複製してから始めてください。

よくある間違い

隣を比べるとき、最後の要素の右隣を見にいってしまうことです。a[j] と a[j + 1] を比べる形にすると、j が末尾に届いた瞬間に存在しない場所を読みます。比べてよいのは「自分の右にまだ要素がある間」だけです。

1. 組み込みのソート関数 (Python の sorted, JS の sort, Go の sort.Slice) は使わない
2. 隣接要素を比較・交換するバブルソートで実装する
3. 戻り値は新しい配列で、入力 arr を破壊的に書き換えない