令和5年度春期 ITストラテジスト 午前Ⅰ 問3

分割手順を追うための視点

クイックソートの分割を考えるときは、各段階で対象範囲と並びの状態がどう変わったかを時系列で整理し、処理の前後に矛盾がないかを落ち着いて確認しましょう。特定の結果を先に決めず、記録の整合性に注目します。

この問題で問われていること

一つの分割操作だけに注目し、開始時の対象範囲、途中で変化する位置関係、終了時に次へ渡される範囲を、問題文の記述と照らして丁寧に確認してください。全体の答えではなく、状態の移り変わりを追うことに集中します。

視点

分割手順は、操作名を暗記するよりも、各段階で何が対象になり、どの情報が更新され、次の段階へ何が引き継がれるかを時系列で記録すると整理しやすくなります。途中の状態を飛ばさず、前後関係の一貫性を確認しましょう。

確認ポイント

• 開始時に確認する対象範囲を特定できているか
• 各段階の変化を順序どおりに記録できているか
• 終了後に次の処理へ渡る範囲を確認できているか

正解

ア

解説

最初は配列左端の2を基準値として分割し、2より小さい1と2より大きい3，5，4に分ける。次に右側グループの左端3を基準値として分割するため、状態は1，2，3，5，4となる。

理由

初回の基準値は配列左端の2です。2より小さい値は1、2より大きい値は3，5，4なので、分割後は1，2，3，5，4となる。

比較

2回目は右側グループ3，5，4の左端にある3を基準値とする。3より小さい値はなく、3より大きい値は5，4であり、配列全体の状態は変わらない。

選択肢ア（正解）

これは正解だよ。初回は左端の2を基準値にし、2より小さい1を左側、2より大きい3，5，4を右側へ分ける。次に右側の左端3を基準値にすると、右側は5，4の順のままなので、2回目終了時はこの並びになる。

選択肢イ

これは不正解だよ。初回の2による分割で、2より大きいグループは元の順番どおり3，5，4となる。2回目はそのグループの左端3を基準値にするため、3より大きい5，4の順序が入れ替わることはなく、この並びにはならない。

選択肢ウ

これは不正解だよ。最初の基準値は2なので、2より小さい1は2の左側へ移る必要がある。また、2より大きいグループは3，5，4の順に保たれる。提示された並びは、初回分割後の配置条件を満たしていない。

選択肢エ

これは不正解だよ。初回の分割では、基準値2より小さい1が左側に置かれるため、1は2より前に現れる。提示された並びでは1が末尾に残っており、基準値より小さい値と大きい値に分ける処理の結果と一致しない。

学習のポイント

クイックソートの基準値選択と、分割後の相対的な順番の扱いを理解する。