令和5年度春期 応用情報技術者試験 午前 問7
配列に格納されたデータ 2，3，5，4，1 に対して，クイックソートを用いて昇順に並べ替える。2回目の分割が終わった状態はどれか。ここで，分割は基準値より小さい値と大きい値のグループに分けるものとする。また，分割のたびに基準値はグループ内の配列の左端の値とし，グループ内の配列の値の順番は元の配列と同じとする。
- ア 1，2，3，5，4
- イ 1，2，5，4，3
- ウ 2，3，1，4，5
- エ 2，3，4，5，1
解答・解説を見る
正解：ア
AI解説
クイックソートは分割のたびに基準値(グループ左端の値)より小さい値・大きい値に分け、各グループ内の順序は元のまま保持する。1回目は全体をピボット2で分割して[1]|2|[3,5,4]となり、2回目は要素が2つ以上ある[3,5,4]をピボット3で分割するが3より小さい値がないため並びは変化せず、結果は1，2，3，5，4のままとなる。 ア: 正解。1回目の分割で[1]|2|[3,5,4]となり、2回目に[3,5,4]をピボット3で分割しても3未満の値がなく並び順は変わらないため、最終的に1，2，3，5，4となる。 イ: 5と4の順序が入れ替わるなど、分割時に元の順序を保持するというクイックソートのルールに反した誤った結果である。 ウ: 1回目の分割自体が誤っており、ピボット2による小さい/大きいグループ分けが正しく行われていない。 エ: 1回目の分割結果としてピボットの2が末尾に来ており、ピボットを小さいグループと大きいグループの間に置くという基本ルールに反する。 💡 クイックソートは「ピボットより小さい要素」「ピボット」「ピボットより大きい要素」の3部構成になり、各グループ内部の相対順序は元の並びのまま保持される点がポイント。要素数1以下のグループはそれ以上分割不要である。
出典：令和5年度 春期 応用情報技術者試験 午前 問7 ／ 独立行政法人情報処理推進機構（IPA）
※Web掲載用に表記を一部変更しています。著作権はIPAに帰属します。
※Web掲載用に表記を一部変更しています。著作権はIPAに帰属します。