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

正解 エ

長さ1の列を、隣どうしで整列済みの列に併合して長さ2、4、8と倍にしていく推移は、マージソートの特徴です。

マージソートは、データ列を細かく分割し、整列済みの部分列どうしを併合（マージ）して長い整列済み列を作る方法です。図の1段目は8個の要素が1個ずつに分割されています。2段目では隣り合う2個ずつが併合され、1 6、3 7、4 8、2 5 となっています。3段目では2個ずつの列が併合され、1 3 6 7 と 2 4 5 8 になります。4段目で最後の併合が行われ、全体が整列されます。

ア：クイックソートは、基準値（ピボット）より小さい値と大きい値に分けて、分割した側を再帰的に整列する方法です。整列済みの列どうしを併合する段階はありません。

イ：シェルソートは、一定間隔ごとに取り出した要素の組を整列し、間隔を狭めていく方法です。隣り合う区間どうしを併合する推移にはなりません。

ウ：ヒープソートは、データをヒープ（親が子以上などの条件を満たす木）に構成し、根の最大値（または最小値）を順に取り出す方法です。データ列を区間に分割して併合することはしません。

出典：平成26年度 秋期 応用情報技術者試験 問6