高校情報I 整列アルゴリズム—比較と交換を分けて配列の変化を一巡ずつ追う｜武蔵野個別指導塾

選択法と交換法の配列を一巡ずつ追い、比較した回数と値を交換した回数を別々に数える練習に取り組めます。

よくあるのは、数を小さい順に並べる問題で、1回の比較を終えた時点で配列全体が整列したと考える場面です。隣り合う2つを調べても、離れた場所にもっと小さい値が残ることがあります。どの場所を調べ、値を動かしたかを分けて記録すると、途中の状態も説明できます。範囲表と授業ノートにある手順を確認してから、以下の例に取り組んでください。

配列のどこまで決まったかを問う

定期テストでは、整列の途中の配列を埋める型があります。最初と最後だけを見比べず、問題で定められた順に比較し、交換が起きたときだけ配列を書き換えます。一巡の区切りも指定を読みます。1回の比較、1回の交換、一巡はそれぞれ異なります。

次に、比較回数と交換回数を数える型があります。比較して順序が正しければ交換しなくても、比較は1回です。選択法では最小値の候補を更新しても、その時点では配列の値を交換しない規則を使います。何を数えるかを余白に書き、比較と交換に別々の印を付けると混同を防げます。

また、途中の答案を直し、その理由を述べる型もあります。結果が昇順でも、指定と違う操作で得た結果なら追跡の答えにはなりません。ここでは小さい値から並べる昇順に限定し、選択法と隣同士の交換法を扱います。処理の速さを表す専門的な記法や探索の手順には広げません。

比較は判断、交換は値の移動

配列は値を順に並べたものです。この記事の添字は左端を1とし、右へ1ずつ増やします。区間の両端は含みます。昇順とは、左から右へ見て、後の値が前の値以上になる順序です。同じ値が隣り合っていても昇順です。図1のように、比較は大小の判断、交換は2か所の値の入れ替えとして区別します。

選択法では、未確定部分の左端から右端まで最小値の位置を探します。左端を最初の候補とし、その右を左から順に候補と比較します。より小さい値を見つけたら候補の位置だけを更新します。等しい場合は候補を変えません。探索後、候補が左端と異なる位置にあれば2つの値を交換し、同じ位置なら交換しません。これで未確定部分の左端が確定します。次の巡ではその右から同様に進めます。

交換法では、未確定部分の左から右へ隣り合う値を比較します。左が右より大きいときだけ交換し、等しいときは交換しません。右へ進むたびに、直前の交換後の配列を使います。一巡すると未確定部分の最大値が右端に移るため、次の巡ではその右端を除きます。最後の1要素は比較せず確定します。図1の比較と交換の区別は両方に共通しますが、確定する端は反対です。

以下は途中で整列しても、指定された巡を最後まで行います。要素が1個以下なら比較も交換も0回です。空の配列もこの規則では操作不要です。交換数は実際に異なる位置の値を入れ替えた回数とし、候補位置の変更や同じ位置との交換を数えません。別の授業では逆向きに走査したり、交換がなければ早く終えたりする場合もあります。その場合は同じ名前でも問題の規則を優先します。

選択法で候補を記録するときは、値だけでなく位置も書くと交換先が明確です。同じ最小値が複数ある場合、値だけを書いても、どの場所と左端を交換するのかは決まりません。ここでは等しい値では候補を更新しないので、未確定部分で最初に現れた最小値の位置を選びます。候補の値と比較する値が同じかどうかも、実際の比較の1回に含まれます。

交換法で右端が確定する理由は、隣同士を左から比べるたび、それまで見た範囲の最大値が比較した組の右側に残るからです。次の値と比べると、より大きい方がさらに右へ残ります。これを右端まで続ければ、その巡の未確定部分の最大値が右端にあります。ただし、残りの部分の順序まで完成したとは限りません。次の巡が必要かどうかは、指定された終了条件で判断します。

回数を表にする際は、巡ごとに「比較」「交換」「巡後の配列」の3つを別の欄に置きます。たとえば比較したが交換しなかった操作にも印を残すと、後から数え直せます。選択法の候補更新は交換欄に入れず、候補の位置を余白に書きます。表の各行は直前の行を引き継ぎ、巡の境界では確定した端を次の範囲から外します。

基本例題: 選択法で左端を決める

4個の整理番号が左から 4、2、3、1 と並んでいます。上の選択法の規則で昇順にします。各巡の終了後の配列と、全体の比較数、交換数を答えてください。番号は練習用に作った値です。図2は各巡の結果を示します。

1. 1巡目の未確定部分は位置1から4です。候補を位置1の4にします。
2. 位置2の2と候補の4を比較し、2の方が小さいので候補を位置2に変えます。配列はまだ変えません。
3. 位置3の3と候補の2を比較します。3は小さくないため候補は位置2のままです。
4. 位置4の1と候補の2を比較し、候補を位置4に変えます。ここまでの比較は3回です。
5. 左端の4と候補の1を交換します。1巡目の結果は 1、2、3、4 です。交換は1回です。
6. 2巡目は位置2から4です。候補の2を3、4と順に比較し、候補は変わりません。左端と候補が同じ位置なので交換しません。
7. 3巡目は位置3と4の値を比較します。3は4以下なので候補は変わらず、交換しません。
8. 各巡の比較数は3、2、1回で、合計6回です。交換数は1、0、0回で、合計1回です。

図2のように、1巡目でたまたま昇順になっても、この問題では残りの巡を行います。2巡目と3巡目の比較を省くと、指定された処理の比較数ではなくなります。一方、既に候補が未確定部分の左端にある巡では、交換を0回と数えます。結果の 1、2、3、4 は元の4個をそれぞれ1個ずつ含み、左から小さい順です。要素の消失や重複がないかも答えを戻して確かめます。

少し難しい例題: 同じ値がある交換法

4枚のカードの値が左から 3、1、3、2 です。前述の交換法で、各巡の終了後の配列、比較数と交換数の合計を答えてください。同じ値は区別せず数値の並びで答え、等しい値は交換しません。早期終了はしません。

1巡目は位置1と2の3と1を比較し、左が大きいので交換して 1、3、3、2 です。次に位置2と3の3と3を比較します。等しいため交換せず、そのままです。最後に位置3と4の3と2を比較し、交換して 1、3、2、3 です。この巡の比較は3回、交換は2回です。右端の3が確定します。

2巡目は位置1と2の1と3を比較し、交換しません。位置2と3の3と2は交換するので、1、2、3、3 です。比較は2回、交換は1回です。3巡目は位置1と2の1と2を比較し、交換しません。したがって各巡後は 1、3、2、3、次に 1、2、3、3、最後も 1、2、3、3 です。比較は合計6回、交換は合計3回です。

最終結果には元の1と2が各1個、3が2個あり、値の個数は変わっていません。等しい3同士の比較も1回に含めたことがポイントです。交換後に次の組を読むので、1巡目の最後には元の位置3の値ではなく、その時点の位置3の値を使います。値が等しい場合に交換する別の規則なら交換回数が変わり得るため、数値の並びが同じでも手順の指定を省けません。

誤答を操作の単位まで戻す

基本例題の1巡目について「最初に4と2を比較したので、結果は 2、4、3、1 で1巡が終了」とする答案を考えます。これは最初の比較だけで巡が終わった誤答です。さらに選択法では、小さい候補を見つけた時点で配列を交換する規則ではありません。図3のように、候補を持ったまま右端まで調べ、最後に左端と交換します。

修正すると、最初の比較後は候補が2に変わるだけで、配列は 4、2、3、1 のままです。その後3、1を候補と比べ、最小の1を選んでから4と交換します。1巡後は 1、2、3、4 です。図3の矢印は、候補更新と実際の交換が別の操作であることを示します。

もう1つの誤りは、交換法で交換した組を次の比較に反映しないことです。比較する位置が右へ移っても、配列は直前の操作後の状態です。比較相手を元の配列から拾うと、値を二重に使ったり見落としたりします。各比較の後に変化した2か所を記録し、変わらない場合も印を付ければ、どの状態から次へ進んだか確認できます。

比較数は要素数だけから決まる場合でも、交換数は初めの並びに左右されます。ここでの4個の処理では、最後まで進むと各巡の比較数は3回、2回、1回です。しかし、交換が必要かどうかはそれぞれの比較結果や選んだ候補の位置を見なければ決まりません。比較数と交換数が同じになるはずだと決めつけず、それぞれの操作を数えます。

答案を検査するときは、最終的に昇順であることに加え、元の値の種類と個数を照合します。交換は2つの値の位置を入れ替えるだけなので、値が増えたり消えたりしません。これが崩れた答案には、書き写しや更新に誤りがあります。ただし値と個数が合うだけでは指定どおりの追跡とは限らないため、各巡の確定位置と比較順も確認します。

自分で追う練習

以下の各問は上で定義した規則を使います。添字は1から始め、途中で並び終えても最後まで処理します。各巡後の値は左から順に書き、回数は整数で答えてください。各問の値と場面は独立しています。

1. 選択法。棚札の番号が 5、1、4、2 です。各巡後の配列と比較数、交換数の合計を求めてください。
2. 交換法。箱の番号が 2、4、1、3 です。各巡後の配列と比較数、交換数の合計を求めてください。
3. 選択法。カードの値が 2、2、1 です。各巡後の配列と比較数、交換数の合計を求めてください。等しい候補は更新しません。
4. 交換法。値が 1、2、3 のとき、各巡後の配列と比較数、交換数の合計を求めてください。さらに値が1個だけの場合の比較数と交換数も答えてください。

答えとたどり方

1. 1巡目は最小の1と5を交換し、1、5、4、2 です。2巡目は残りの最小の2と5を交換して 1、2、4、5 です。3巡目は4と5を比べて交換せず、1、2、4、5 です。比較は3、2、1回の計6回、交換は2回です。元の1、2、4、5が各1個残り、昇順になっています。

2. 1巡目は2と4を交換せず、4と1、続いて4と3を交換して 2、1、3、4 です。2巡目は2と1を交換し、2と3は交換せず 1、2、3、4 です。3巡目も交換せず同じ並びです。比較は計6回、交換は計3回です。4が右端へ移った後も残りを調べることと、元の4個が各1個あることを確かめます。

3. 1巡目は最初の2を候補にし、次の2では候補を変えず、1で候補を更新します。左端と交換して 1、2、2 です。2巡目は2同士を比較し交換せず、1、2、2 です。比較は2回と1回の計3回、交換は1回です。元の2が2個残っているため、同値の一方を失っていません。

4. 1巡目も2巡目も 1、2、3 です。比較は2回と1回の計3回で、交換は0回です。既に昇順でも早期終了しない指定なので比較は残ります。1個だけなら隣り合う組がないため比較も交換も0回です。どちらも元の値と個数を保っています。もし早期終了の規則が問題にあれば、その条件を満たしたところで以後の比較を行わず、回数を数え直します。

答えを出す前の短い確認

比較は大小の判断、交換は値の入れ替えです。
選択法は未確定部分の左端を確定します。
ここでの交換法は未確定部分の右端を確定します。
等しい値や交換しない場合も比較を数えます。
巡の範囲と終了条件は問題の指定に従います。

記録からつまずきを見つける

途中の配列が合わないときは、最初に違った比較まで戻ります。比較する位置が違うのか、大小の判断が違うのか、交換後の値を次へ引き継いでいないのかを切り分けます。最終結果だけが合っていても、巡の途中に別の操作を入れていないか確認します。

個別指導では、本人が書いた候補位置や比較の印を見ながら、次に比べる2つと、その理由を言葉で確かめます。回数だけ間違えた場合は、交換しなかった比較や最後の巡を指で数え直します。同じ値と1個の配列も試すと、条件の境界を理解しているか見えます。配列の変化を1操作ずつ説明できれば、初めて見る並びにも手順を当てはめられます。