平成26年度秋期 応用情報技術者試験 午前 問6

正解：エ

AI解説

図はデータ列がまず細かく分割され(区切り線が増え)、その後、隣り合う部分列どうしが併合(マージ)されて整列済みの長い列に統合されていく過程を示している。「分割してから整列済み列を併合する」のはマージソートの特徴である。マージソートは分割統治法に基づき、計算量は常にO(n log n)で安定なソートである。 ア: クイックソートは基準値(ピボット)より小さい群と大きい群に分割を繰り返す方式で、併合の過程はない。分割位置もデータ依存で不均等になる。 イ: シェルソートは一定間隔おきに取り出した要素群ごとに整列し、間隔を徐々に狭めていく方式で、図のような分割・併合の形にはならない。 ウ: ヒープソートはヒープ(半順序木)を構成して最大値(最小値)を順に取り出す方式で、列の分割は行わない。 エ: 正解。列を分割し、整列しながら併合していく図の推移はマージソートである。 💡 整列過程の図の見分け方:「半分ずつ分割→併合」ならマージソート、「ピボットで左右に振り分け」ならクイックソート、「先頭部分だけ整列が進む」なら選択・挿入系と判断する。