アルゴリズム図鑑
挿入ソート
左側の整列済みの部分に、次の要素を正しい位置まで差し込んでいく整列法です。トランプの手札を並べるときの動きに似ています。
考え方
- 差し込む値を key に取っておき、それより大きい値を1つずつ右へずらす
- ずらし終わった位置（j + 1）に key を入れる
- ほぼ整列済みのデータでは、ずらす回数が少なく速い
計算量
O(n²)
試験でのポイント
- while の条件「j ≧ 1 and data[j] > key」は、左から順に判定され、j が 0 になると右側は調べない
- 最後に data[j] ではなく data[j + 1] に入れるところが空欄で問われやすい