1 歩ずつ動かす
[5, 2, 8, 1, 9, 3, 7, 4] を小さい順に並べる
- 50
- 21
- 82
- 13
- 94
- 35
- 76
- 47
- 比較中
- 入れ替えた
- 位置が決まった
- いま扱う範囲
- 箱の上の字は、いまの最小の候補
- 箱の下の数字は添字
1 歩目 / 全 37 歩比べた回数 0 回入れ替えた回数 0 回
8 個の値を小さい順に並べます。右の並んでいない範囲から最小を探し、左端と入れ替えていきます。
いま動いている疑似コードの行
- 1i を 0 から n - 2 まで 1 つずつ増やす
- 2min = i (いまの最小の候補)
- 3j を i + 1 から n - 1 まで 1 つずつ増やす
- 4a[j] < a[min] なら min = j
- 5a[i] と a[min] を入れ替える (添字 i が決まる)
見本を変える
予想してみる
いまは 1 歩目です。
次に比べる添字 1 の値は、いまの最小の候補 (添字 0) より小さいでしょうか。
今回わかること
- 並んでいない範囲から最小を選び、左端と入れ替える流れ
- どんな入力でも比べる回数が変わらず、入れ替えは少なくて済む理由
前提
- 配列と添字 (0 から数える番号)
- for 文の二重の繰り返し
- 最小の値の添字を覚えておく書き方
どんな並べ方か
選択ソートは、まだ並んでいない範囲の中から最小の値を探し、その範囲の左端の値と入れ替える並べ方です。これを繰り返すと、左から順に小さい値が決まっていきます。
探すときに比べるだけで、動かすのは最後の入れ替え 1 回です。そのため、入れ替えの回数は多くても n - 1 回に収まります。
手順と具体例
- 1並んでいない範囲の左端を、最小の候補にする
- 2右へ 1 つずつ見て、候補より小さい値があれば候補を替える
- 3範囲の右端まで見たら、候補の値を左端の値と入れ替える
- 4左端の位置が決まるので、範囲を 1 つ狭める
- 5残りが 1 個になるまで繰り返す
| 区切り | 比べた / 入れ替えた | 終わったときの並び |
|---|---|---|
| 1 回目 (添字 0 を決める) | 7 回 / 1 回 | 1, 2, 8, 5, 9, 3, 7, 4 |
| 2 回目 (添字 1 を決める) | 6 回 / 0 回 | 1, 2, 8, 5, 9, 3, 7, 4 |
| 3 回目 (添字 2 を決める) | 5 回 / 1 回 | 1, 2, 3, 5, 9, 8, 7, 4 |
| 4 回目 (添字 3 を決める) | 4 回 / 1 回 | 1, 2, 3, 4, 9, 8, 7, 5 |
| 5 回目 (添字 4 を決める) | 3 回 / 1 回 | 1, 2, 3, 4, 5, 8, 7, 9 |
| 6 回目 (添字 5 を決める) | 2 回 / 1 回 | 1, 2, 3, 4, 5, 7, 8, 9 |
| 7 回目 (添字 6 を決める) | 1 回 / 0 回 | 1, 2, 3, 4, 5, 7, 8, 9 |
比べる回数と計算量
| 場合 | 比べる回数 | 計算量 |
|---|---|---|
| もう並んでいる | n(n - 1) ÷ 2 回 | O(n²) |
| ばらばら | n(n - 1) ÷ 2 回 | O(n²) |
| 逆順 | n(n - 1) ÷ 2 回 | O(n²) |
8 個なら、どんな並びでも 28 回比べます。入れ替えは多くても 7 回で、もう並んでいれば 1 回もありません。
使いどころ
向いているとき
- 値を動かす手間が大きく、入れ替えの回数を減らしたいとき
- 要素が数十個までの、小さい配列のとき
- 並べ替えの仕組みを、順を追って学ぶとき
向いていないとき
- ほとんど並んでいる配列 (挿入ソートやバブルソートのほうが早く終わる)
- 同じ値の順番を崩したくないとき (入れ替えで順が変わる)
コード
疑似コード
- 1i を 0 から n - 2 まで 1 つずつ増やす
- 2min = i (いまの最小の候補)
- 3j を i + 1 から n - 1 まで 1 つずつ増やす
- 4a[j] < a[min] なら min = j
- 5a[i] と a[min] を入れ替える (添字 i が決まる)
実際のコード
python実行可能
出力
▶ 実行ボタンを押すと結果がここに表示されます
Python と JavaScript は、書き換えて「実行」を押すと、その場で結果が出ます。Java は読むだけの欄です。
よくある疑問
- もう並んでいる配列でも、なぜ比べる回数が減らないのですか？
- 最小がどこにあるかは、右端まで見ないと分からないからです。途中で止められる目印がないので、どんな入力でも同じ回数だけ比べます。
- 選択ソートは、なぜ安定な並べ方ではないのですか？
- 左端の値を遠くの最小と入れ替えるので、同じ値を追い越すことがあるからです。たとえば 2, 2, 1 を並べると、先にあった 2 が後ろへ飛び、2 つの 2 の順番が入れ替わります。
