選択ソート
残りの中から最小値を探し、次の位置に入れ替えます。入れ替えはとても少ないですが、比べる回数はいつも同じです。
- Ω(n²)
- Θ(n²)
- O(n²)
- O(1)
- いいえ
- はい
最良: この方法にとって一番楽な入力のとき、リストのサイズ n に応じて時間がどう増えるか。
平均: ふつうの場合に、n に応じて時間がどう増えるか。n² なら値の数が2倍で時間は約4倍。n log n はずっとゆっくり増えます。
最悪: 一番難しい入力での増え方。速さが決して落ちてはいけないときに役立ちます。
メモリ: リストのほかに必要な追加メモリの量。1 なら変数がいくつかだけ、n ならリストのコピー1つ分です。
安定: 同じ値どうしが元の順番を保ちます。レコードを1つの項目で並べ替えるときに大切です。
追加メモリ不要: 2つ目のリストを使わず、リストそのものの中で並べ替えます。
- 比較中
- 移動中
- 今の最小値
- 位置が確定
試してみましょう: 逆順のリストを選んでください。比べる回数は、ほかのどのリストともまったく同じです。
仕組み
まだ並んでいない部分を見て、最小値を探します。それを並んでいない部分の先頭の値と入れ替えると、もう1つの値の位置が確定します。リストが最初から並んでいても、残りの値を毎回すべて確かめます。
向いている場面
データを読むのは簡単でも、動かすのに手間がかかる場合に役立ちます。入れ替えは1つの位置につき多くても1回だからです。それ以外なら、簡単な方法の中では挿入ソートの方が向いています。