| English | 意味 |
|---|---|
| Sorting/ˈsɔːtɪŋ/ | ソート |
| selection sort/sɪˈlekʃn sɔːt/ | 選択ソート |
| insertion sort/ɪnˈsɜːʃn sɔːt/ | 挿入ソート |
| in place/ɪn pleɪs/ | インプレイース |
整列
- ソート は要素を並べ替えること（例えば从小到大）。
- APコースでは2つの単純なソート法を扱います: 選択ソート と 挿入ソート。
- どちらも 重複ループ を使用し、要素をスワップまたはシフトして配置します。
- ソートしておくことで、後に高速な 二項検索 を利用できるようになります。
選択ソート
- 残りの要素の中で最小のものを見つけ、先頭と交換する。
- 次に残ったものの中から最小のものを finding し、次の位置に移動させ、これを繰り返す。
- アレイの先頭は整列済みになり、後方は未整列として縮小していく。
- パスごとに1回の交換だが、各パスで残りの要素をすべてスキャンする必要がある。
挿入ソート
- 次の要素を取り出し、すでに整列済みの先頭部分に正しい位置へ戻し（シフト）て挿入する。
- カードの手牌を並べ替えるように、新しいカードを適切な位置に差し込む。
- パスごとに整列領域が1つ増える。
- データが既にほぼ整列されている場合に高速である。
処理量
- 両方のソートは二重ループを用いるため、最悪の場合、
n²回の比較を行う。 - 小規模なアレイには適しているが、非常に大きなデータでは遅い。
- インプレイスで動作するため、追加のアレイは不要である。
- 試験では単に名前を答えるだけでなく、**トレース（追跡）**することが求められる。
選択ソートは「残りの最小要素」を先頭と「交換」し、挿入ソートは「新しい要素」を整列部分へ「戻して挿入」する——混同しないように注意。 どちらも二重ループによるインプレイスソートであり、O(n²) の処理量を持つ。名前を暗記するのではなく、パスごとのアレイの状態を追跡してトレースすること（AP試験ではパス完了後の状態を問われる）。
[3, 1, 2] に対する選択ソート:
- パス1: 最小値は
1；先頭と交換 →[1, 3, 2]。 - パス2: ⟨
[3, 2]⟩ の中での最小値は2；交換 →[1, 2, 3]。 - 整列完了 — パスごとに先頭が1つずつ増えた。
ソートとは順序を整えること。選択ソートは「残りの最小要素」を繰り返し先頭と交換し、挿入ソートは「新しい要素」を順に整列部分へ戻して挿入する。どちらも二重ループ、インプレイス、O(n²) のソートである。ソートによってその後の高速な二分探索が可能になる。
ソートの進行状況を確認する
各パスでさらに1つの要素が正しい位置に配置される。
選択ソートは...によって動作する
難易度 1/5 · 100 コイン + 今日初回完了時に小ボーナス付与
選択ソートは最小値を選択し、前に移動させる。
挿入ソートは...によって動作する
難易度 1/5 · 100 コイン + 今日初回完了時に小ボーナス付与
挿入ソートは各要素を正しい整列済み位置に挿入する。
最悪の場合、両方のソートは約...を行う
難易度 1/5 · 100 コイン + 今日初回完了時に小ボーナス付与
ネストループは O(n²) となる。
選択ソートと挿入ソートはともにインプレイ（追加配列なし）で動作する。
難易度 1/5 · 100 コイン + 今日初回完了時に小ボーナス付与
同じ配列を再編成する。
[3, 1, 2] に対する選択ソートのパスを並べ替えてください。
難易度 3/5 · 200 コイン + 今日初回完了時に小ボーナス付与
先頭部分は並べ替えられ、各反復で1つ増える。
最初にソートしておくと有用です。なぜなら、後で...可以使用するからです。
難易度 1/5 · 100 コイン + 今日初回完了時に小ボーナス付与
二項探索には整列されたデータが必要。