未確定部分の最小値を見つけ、その先頭と交換します。左から順に位置が確定します。

選択ソートを棒グラフで示すシミュレーター

再生・ステップ実行・スライダーで操作できます。ピンクは現在見つかっている最小値です。

最良O(n²)

平均O(n²)

最悪O(n²)

追加領域O(1)

安定いいえ

最大交換回数n − 1

比較は多く、交換は少ない

整列済みでも最小値を探すために残りの全要素を調べます。一方、1周の交換は最大1回なので、比較よりデータ移動のコストが大きい場合に有利なことがあります。

なぜ不安定なのか

「重複が多い」を最後まで実行し、同じ値のa/bラベルを比較してください。離れた位置との交換により、移された値が同じ値を飛び越え、元の順序が逆転することがあります。

演習

応用として、k周で止めると小さい方からk個をO(nk)で得られます。また、相異なる要素の置換を整列する最小交換回数は、要素数から置換のサイクル数を引いた値になります。