選択ソート

入れ替えの回数が多すぎる

バブルソートは、隣どうしを見ては入れ替えていました。[5, 4, 3, 2, 1] のような逆順を入れると、比較のたびに入れ替えが起きます。並べ替え自体は正しく終わりますが、そのために配列へ 10 回も書き込んでいます。

1 回の入れ替えは、値を 3 回書き換える操作です。10 回の入れ替えなら 30 回の書き込み。しかも、いま右へ押し出した 5 を、次の比較でまた押し出しています。同じ値を何度も運んでいるわけです。

書き込みは比較よりも高くつきます。フラッシュメモリのように書き換え回数に寿命がある媒体では、なおさら差が出ます。そこで発想を変えます。どこへ何を持ってくるかを先に決めてから、1 回だけ動かすのです。

値ではなく「位置」を覚えておく

[4, 2, 7, 1, 3] の先頭に置くべきなのは、全体の最小値の 1 です。ここで欲しいのは値そのものではなく、それが何番目にいるかです。番号さえ分かれば、先頭と 1 回入れ替えるだけで済みます。

いちばん小さいものの居場所を探す部品を、テストの点数で見てみます。

比べているのは scores[i] と、その時点でいちばん低い点です。より低い点に出会ったときだけ、覚えている番号を書き換えます。この間、配列そのものは一度も触っていません。

1 周で 1 つずつ、左から確定させる

[4, 2, 7, 1, 3] を最後まで追います。

• 全体の最小は 1（4 番目）。先頭の 4 と入れ替えて [1, 2, 7, 4, 3]
• 2 番目から先の最小は 2。すでにその位置にいるので入れ替えなし
• 3 番目から先の最小は 3。7 と入れ替えて [1, 2, 3, 4, 7]
• 4 番目から先の最小は 4。動かさない

入れ替えは 2 回だけでした。比較の回数はバブルソートと変わりませんが、書き込みの回数は要素数を超えません。

同じ点数の 2 人が、勝手に入れ替わる

弱点もあります。[(5, "あ"), (5, "い"), (3, "う")] を数値で並べ替えると、1 周目で先頭の (5, "あ") と最小の (3, "う") が入れ替わり、[(3, "う"), (5, "い"), (5, "あ")] になります。もとは「あ」が先だったのに、後ろへ回されました。

同じ値どうしの元の並びが保たれる並べ替えを安定と言います。バブルソートは隣どうししか入れ替えないので、同じ値を飛び越えることがなく安定です。選択ソートは離れた位置と入れ替えるため、間にいる同じ値をまたいでしまい、安定ではありません。

並べ替えるのが数値そのものなら、入れ替わっても見分けがつかないので困りません。効いてくるのは「点数の高い順に並べつつ、同点なら受付順のまま出したい」ような場面です。

1. 組み込みのソート関数 (Python の sorted, JS の sort, Go の sort.Slice) は使わない
2. 各ラウンドで未確定領域の最小値を選んで、先頭の要素とスワップする
3. 戻り値は新しい配列で、入力 arr を破壊的に書き換えない