平成26年度 秋期 午前 問6

✓ これが正解エマージソート

解説

区切りが 8、4、2、1 と半分ずつ減ります。

設問は、データ列が上から下へ推移する図を見せて、どの整列方法かを当てさせています。見分けの軸は、数の動きではなく区切りの数が増えるのか減るのかという一点です。図の 1 行目は縦線で 8 つに割れており、どの組も 1 要素です。2 行目は 4 つの組になり、どの組も 2 要素で、しかも組の中は昇順に並んでいます。3 行目は 2 つの組で各 4 要素、4 行目は区切りが消えて全体が昇順です。つまり組の数は 8、4、2、1 と半分ずつ減っており、これは整列済みの小さな組を 2 つずつ突き合わせて 1 つにまとめる操作を繰り返した跡です。実際に突き合わせてみると、6 と 1 から 1 と 6 の組、7 と 3 から 3 と 7 の組ができ、次の行では 1 と 6 の組と 3 と 7 の組を先頭から比べて 1、3、6、7 が得られます。最後に 1 3 6 7 と 2 4 5 8 を同じように比べれば全体が昇順になります。この積み上げ方をする整列がマージソートです。

ほかの選択肢はなぜ違うのか

• アクイックソート：基準値を決めて大小に振り分ける方法では、分割が先に起きるので最初の行に縦線が入らず、全体がひと続きの状態から始まります。また振り分けた直後の組の中はまだ並んでおらず、組の大きさもきれいに半分ずつにはなりません。
• イシェルソート：離れた位置どうしを比べ、その間隔を少しずつ詰めながら整えていく方法です。列そのものを割らないので、図にある縦の区切り線が何を表しているのか説明できません。
• ウヒープソート：木の形に組み替えて最大の要素を末尾へ移すことを繰り返す方法です。確定していくのは後ろからなので、途中の行は末尾だけが並んだ姿になり、前から組ごとに整っていく図とは合いません。