選択ソート
選択ソートは、多くの人が手札のトランプを並べるのと同じやり方でリストを並べ替えます。最小のものを見つけて先頭に置き、残りの中からまた最小のものを探します。比較は多いものの交換はごくわずかで、実行時間はリストの並びにほとんど左右されません。
考え方
リストを、左側の整列済み部分(最初は空)と右側の未整列部分に分けます。未整列部分を走査して、最小値の位置を覚えておきます。その値を未整列部分の先頭の値と交換すると、整列済み部分が1つ増えます。値が1つだけ残るまで繰り返します。最後の値は必ず最大値です。
例
5, 1, 4, 2, 8 を考えます。1回目のパスは5つの値をすべて走査し、最小の1を見つけて5と交換します:1, 5, 4, 2, 8。2回目のパスは 5, 4, 2, 8 を走査し、2を見つけて5と交換します:1, 2, 4, 5, 8。3回目のパスでは4が、4回目のパスでは5がすでに確定位置にあるので、何も動きません。比較は 4 + 3 + 2 + 1 = 10 回、交換はわずか2回です。同じリストでバブルソートは4回交換します。
比較回数は常に同じ
どの値が最小かを確かめるには、残っている値をすべて見る必要があります。パス1ではn − 1回、パス2ではn − 2回と比較し、最後は1回で、合計するとn(n − 1)/2回になります。この回数はリストによりません。整列済みのリストでも逆順のリストでも比較回数はまったく同じです。選択ソートには早期終了がありません。最小値がすでに先頭にあると分かっても、残りについては何も分からないからです。
交換は少ない
各パスの交換は最大1回なので、選択ソートの交換はn − 1回を超えず、最小値がすでに確定位置にあれば交換を省きます。バブルソートや挿入ソートの交換回数は順序が逆のペアの数と同じで、約n²/2回になることもあります。書き込みのたびに劣化するメモリなど、値の書き込みが2つの値の読み出しよりずっと高くつく場合、交換が少ないことは利点になります。
安定ではない
等しい値が元の順序を保つソートを安定といいます。選択ソートは安定ではありません。離れた位置との交換で、ある値が等しい値を追い越すことがあるからです。2, 2, 1 では、1回目のパスで最初の2と1が交換されて 1, 2, 2 となり、2つの2の順序が逆になります。交換の代わりに間の値をずらす版は安定ですが、動かす値がずっと多くなります。
試してみよう
アプリを開いて「再生」を押すか、「ステップ」で比較を1回ずつ進めます。走査中の値が強調表示され、現在の最小値には専用の色が付き、各パスは左側の整列済み部分への交換で終わります。整列済みのリストと逆順のリストを試してみましょう。比較回数は同じで、交換回数だけが違います。
よくある質問
選択ソートの時間計算量は?
どの場合もO(n²)です。n個の値に対して、並びに関係なく比較はちょうどn(n − 1)/2回です。交換は最大n − 1回で、追加メモリはO(1)しか必要ありません。
選択ソートとバブルソートの違いは?
バブルソートは進みながら隣り合う値を交換し、交換のないパスがあれば早く終われます。選択ソートは最小値の位置だけを覚えておき、各パスの最後に1回だけ交換します。交換が少ないのは選択ソート、ほぼ整列済みのリストで速いのはバブルソートです。
選択ソートは安定ですか?
いいえ。交換によって、ある値が等しい別の値を追い越すことがあるため、等しい値の順序が変わることがあります。交換の代わりに値をずらせば安定にできますが、移動が増えます。
ヒープソートと選択ソートの関係は?
ヒープソートは、次の値をより速く見つける選択ソートです。未整列部分をヒープに保つので、各選択は全体の走査ではなく約log nステップで済みます。これで全体がO(n log n)に下がります。
試してみますか?
ブラウザで PictorX を開きます。インストール不要、始めるのにクレジットカードも不要です。
選択ソートを試す