---

挿入ソート

---

N個のデータが，配列 a[0]〜 a[N-1]に格納されているとする．

挿入ソート：

1. a[1]をリスト(a[0])の適切な位置(a[1]が小さければ前，大きければ後ろ)に挿入する
2. 小さい順に並ぶよう，a[2]をリスト(a[0], a[1])の適切な位置に挿入
3. 小さい順に並ぶよう，a[3]をリスト(a[0], a[1], a[2])の適切な位置に挿入
4. 小さい順に並ぶよう，a[4]をリスト(a[0]〜 a[3])の適切な位置に挿入
5. ...
6. 小さい順に並ぶよう，a[N-1]をリスト(a[0]〜a[N-2])の適切な位置に挿入

      for(k=2; k<N; k++) {
              小さい順に並ぶよう，a[k]をリスト(a[0]〜a[k-1])の適切な位置に挿入
      }

小さい順に並ぶよう，a[k]をリスト(a[0]〜a[k-1])の適切な位置に挿入する操作 :

• 後ろから順に比較することで，リスト(a[0]〜a[k-1])中の a[k] が入るべき位置を探し，
• そこに a[k] を挿入する

  この操作の詳細化

  1. a[k]の値を作業用の変数 tに退避して，k番目の位置を空欄にする (t ← a[k])
  2. tとa[k-1]を比較する
     • t < a[k-1] ならば ，
       挿入する位置はもっと前にあるので， a[k-1] を空欄になっている k 番目位置(1つ後ろ)にずらし， k-1番目の位置を空にして，次のステップへ
     • t >= a[k-1]ならば，
       挿入すべき位置(k)がみつかったので， 操作を終了する
  3. tとa[k-2]を比較する
     • t < a[k-2] ならば ，
       挿入する位置はもっと前にあるので， a[k-2] を空欄になっている k-1 番目位置(1つ後ろ)にずらし， k-2番目の位置を空にして，次のステップへ
     • t >= a[k-2]ならば，
       挿入すべき位置(k-1)がみつかったので， 操作を終了する
  4. tとa[k-3]を比較する
     • t < a[k-3] ならば ，
       挿入する位置はもっと前にあるので， a[k-1] を空欄になっている k-2 番目位置(1つ後ろ)にずらし， k-3番目の位置を空にして，次のステップへ
     • t >= a[k-3]ならば，
       挿入すべき位置(k-2)がみつかったので， 操作を終了する
  5. ...
  6. tとa[0]を比較する
     • t < a[0] ならば ，a[0]〜a[k]のどれよりも小さいので， a[0] を空欄になっている 1 番目位置(1つ後ろ)にずらす
       tを挿入する位置は0

  プログラミングに向けての詳細化： a[k]をリスト(a[0]〜a[k-1])の適切な位置に挿入する

  1. t ← a[k]
  2. m ← k-1
  3. t < a[m] が成立する間，以下の操作をくり返す：
     • a[m+1] ← a[m] (1つ後ろへ移動する)
     • m--

  プログラミングへの具体化： a[k]をリスト(a[0]〜a[k-1])の適切な位置に挿入する

        t ← a[k];
        m ← k-1;
        while( (m>=0) && (a[m] > t) ) {
            a[m+1] < a[m];
            m--;
        }
        a[m+1] ← t;