プログラム 挿入法 仕組み
基本情報技術者試験H19春午後問４
過去問
【プログラムの説明】
整列型の一次元配列の要素A[0],…A[N](N>0)を、挿入ソートで昇順に整列する副プログラムInsertSortである。
(1) 挿入ソートの手順は、次の通りである。
①まず、A[0]とA[1]を整列し、次にA[0]からA[2]までを整列し、その次にA[0]からA[3]までというように、整列する区間の要素をひとつずつ増やしていき、最終的にA[0]からA[N]までを整列する。
→左から一個ずつ整列していく
②整列する区間がA[0]からA[M](1≦M≦N)までのとき、A[M]を既に整列された列A[0],…A[M-1]中の適切な位置に挿入する。その手順は以下の通りである。
(a) A[M]の値を、作業領域Tmpに格納する。
→格納された値は、挿入する目的を持っている。
(b) A[M-1]からA[0]に向かってTmpと比較し、Tmpよりも大きな値を順次隣(要素番号の大きい方)に移動する。
→後で挿入するために別の場所Tmpにいったん避難させておき、
Tmpを挿入する位置を空けるために、いままで入っていた値をずらしてあげる。
(c) (b)で最後に移動した値の入っていた配列要素にTmpの内容を格納する。(b)で移動がなかった場合にはA[M]に格納する。
→場所をゆずってくれたので、避難していたTmpをその位置に挿入する。
そもそもあらためて並び替える必要がない(挿入しなくて良い)場合は、
同じ位置に格納する。
(2) 副プログラムInsertSortの引数の仕様を表に示す。
◯InsetSort (整数型:A[],整数型:N)
◯整数型：Idx1, Idx2, Tmp
◯論理型：Loop
■ Idx1:1, Idx1 ≦ N, 1 →Idx1は初期値が1、N以下のときにループし、1ずつ増加する
| ・Tmp ←A[Idx1] →A[Idx1]を後で挿入するために、一旦Tmpに格納(避難)する
| ・Idx2 ←？
→①A[Idx1]は現在一番右の数字であり、それを左側の既に整列されている部分に挿入したい。
そのためには、一番右の数字とそのひとつ左横の数字を比べる必要がある。
今、一番右の数字はA[Idx1]で、ひとつ左横はA[Idx1-1]にあたる。
→②Idx1は定義(初期化)されているのに対して、Idx2は初期化されていない。
Idx1とひとつ左横のIdx1-1を比較するために変数Idx2が設定されていると考えられるので、変数Idx2にIdx1-1を代入するのが妥当。
| ・Loop ← true
→Loop変数に、trueを代入することで、下のループが実行される。
Loop = trueにならないと、下の作業は実行されない。
| ■Idx2 ≧ 0 and Loop = true
→上で、Loop←trueが代入され、かつIdx2が0以上のときループが実行される。
| | ↑ A[Idx2] ＞ Tmp
→比較対象のA[Idx2]が、Tmpより大きい場合。
| | | ・？
→A[Idx2]が現在存在する位置もしくはそれより左に、Tmpを挿入しなくてはならないので、A[Idx2]をひとつ右つまり、Idx2+1の位置にずらしてこなければならない。
| | | ・Idx2 ← Idx2 - 1
→Idx2よりひとつ左にあるIdx2-1の位置を、新たなIdx2の位置として再定義する。
Idx2は、Tmp(A[Idx1])と数の大小関係を比較する対象の位置を示す変数であり、
その位置の範囲は0からIdx1-1の間であり、最初Idx1-1とIdx1を比較し、
Idx1の方が小さければ、順次より左の位置の数字とIdx1を比較する必要がある。
ここで行われているのは、Tmpとの比較対象の位置をひとつ左にずらす行為。
| | | ーーーーーーーーーーーー
| | | ・Loop ← false
→比較対象のA[Idx2]が、Tmpより小さい場合は、Loop関数にfalseを代入する。
すると、Loop=trueではなくなるので、ループが実行されなくなる。
| | ↓
| ■
| ・？
→挿入するために作ったTmpを最終的にあるべき場所に挿入する。
直前のループで、A[Idx2]がTmp以下になった時点でループは終了している。
Tmpは大小関係によって挿入位置を決め、その順番は昇順である。
A[Idx2]が初めてTmp以下になったということは、A[Idx2]の直後の位置にTmpが入るということなので、Tmpが入る位置はIdx2+1になる。
よって、A[Idx2+1]←Tmp
■
