c言語の挿入ソートについての質問です。

Question

c言語で挿入ソートを調べながら書きました。
void insertionSort (int array[], int array_size) {
int i, j, key;

for (j = 1; j < array_size; j++) {
    key = array[j];
    i = j - 1;

    while ((i >= 0) && (array[i] > key)) {   //keyとその左隣の大小を比べる
        array[i + 1] = array[i]; //i番目の要素がkeyよりも大きい場合、i番目とi＋１番目を入れ替える
        i--;  //iを一つ下げる.iが０以上ならwhileの中を繰り返す
    }
    array[i + 1] = key;
}

}
しっかり動きはするのですが、なぜ最後にarray[i + 1] = keyを書くのかが理解できません。初学者なのでわかりやすく教えていただけないでしょうか。

Answer 1

key = array[j];

keyに最初の要素を取り出しておいて、
それ以降、keyより大きければ１つづつ上に詰めていって、最後の空いたところに、keyを入れてるんです。
これで、他より小さい値が後ろに行くことになります

Comments

[MyonMyon]

keyに値を取り出しておくという考え方だったのですね。で、空いたところにkeyを入れると。とてもわかりやすかったです。ありがとうございます。すでにベストアンサーを定めてしまったのですが、こちらもベストアンサーでした。

Answer 2

以下の行で元々array[i+1]に入ってた値はarray[]のどこに格納すべきか考えるとわかると思います。

array[i + 1] = array[i]

Comments

[MyonMyon]

回答ありがとうございます。コメントに書いているようにarray[i+1]=array[i]の操作を値の入れ替えと思ってしまっていて、頭がこんがらがっていました。入れ替えではなく代入でしたね。そう考えると納得できました。感謝します