選択ソート

残りの中から最小値を探し、次の位置に入れ替えます。入れ替えはとても少ないですが、比べる回数はいつも同じです。

• 最良 Ω(n²)
• 平均 Θ(n²)
• 最悪 O(n²)
• メモリ O(1)
• 不安定
• 追加メモリ不要

用語の意味

• 最良: この方法にとって一番楽な入力のとき、リストのサイズ n に応じて時間がどう増えるか。
• 平均: ふつうの場合に、n に応じて時間がどう増えるか。n² なら値の数が2倍で時間は約4倍。n log n はずっとゆっくり増えます。
• 最悪: 一番難しい入力での増え方。速さが決して落ちてはいけないときに役立ちます。
• メモリ: リストのほかに必要な追加メモリの量。1 なら変数がいくつかだけ、n ならリストのコピー1つ分です。
• 安定: 同じ値どうしが元の順番を保ちます。レコードを1つの項目で並べ替えるときに大切です。
• 追加メモリ不要: 2つ目のリストを使わず、リストそのものの中で並べ替えます。