平成28年度秋期 ITストラテジスト 午前Ⅰ 問3

整列手順を一段階ずつ追って見分ける

整列の手法同士を区別するときは、名称の印象ではなく、処理を一回進めたときにデータ列の状態がどう変わるかに着目すると判断しやすくなります。小さな例を自分で用意し、一段階ずつ状態を書き出して比べる姿勢が有効です。

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

問われているのは、ある整列手法の処理の進み方を他の手法と取り違えずに識別できるかです。一回の操作を終えた時点でデータ列のどこがどう変化したかという一点に絞り、与えられた情報と照らし合わせて検討してください。

視点

整列アルゴリズムは、最終的に昇順や降順の結果を得る点では共通していても、途中経過の作り方はそれぞれ異なります。そのため、区別の手がかりは完成形ではなく途中の状態にあります。自分で数個の値を並べた例を用意し、手順を一段階だけ進めた結果を書き出します。そのうえで、その結果が問題で示される手順の特徴と矛盾しないかを確かめます。この流れで考えると、名前や印象の似た手法に惑わされにくくなります。

確認ポイント

• 数個の値で小さな例を作り、手順を一段階だけ進めた後の並びを書き出したか
• その一段階で、データ列のどの範囲が変化し、どの範囲が変化していないかを確認したか
• 書き出した途中状態が、問題で示された手順の特徴と食い違わないかを照合したか

正解

エ

解説

ヒープソートは、未整列の部分を順序木（ヒープ）に構成し、根から最小値を取り出して整列済の部分に移す操作を繰り返す整列法だよ。そのため正解はエで、ア・イ・ウはそれぞれシェルソート、クイックソート、バブルソートの説明だよ。

理由

ヒープソートでは、未整列のデータを順序木（ヒープ）に組み立てるよ。ここでのヒープは、親の値が子の値以下になる条件を満たす木だよ。すると根に最小値が来るので、それを取り出して整列済の部分に移すよ。残りを再び順序木に整えて同じ操作を繰り返すと、未整列の部分がだんだん縮んで整列が完了するよ。エはこの手順と一致しているよ。

比較

アは間隔を空けた部分列を整列しながら間隔を詰めていくシェルソートだよ。イは基準値で大小の区分に振り分けて再帰的に処理するクイックソート、ウは隣り合う要素を比較・交換するバブルソートだよ。どれも順序木から最小値を取り出す手順を含まないから、ヒープソートの説明には当たらないよ。

選択肢ア

これは不正解だよ。一定の間隔おきに取り出した要素から成る部分列をそれぞれ整列し、間隔を詰めながら最後は間隔1で仕上げる方法はシェルソートだよ。離れた要素同士を先に大まかに並べておく手法で、順序木を作って最小値を順に取り出すヒープソートの手順とは違うよ。

選択肢イ

これは不正解だよ。中間的な基準値（ピボット）を決め、それより大きい値の区分と小さい値の区分に要素を振り分け、それぞれの区分で同じ処理を繰り返すのはクイックソートの説明だよ。分割を繰り返して区分を細かくしていく手法で、順序木から最小値を取り出すヒープソートとは別物だよ。

選択肢ウ

これは不正解だよ。隣り合う要素を比較し、大小の順が逆なら入れ替える操作を繰り返すのはバブルソート（隣接交換法）の説明だよ。比較の相手は常に隣の要素で、木構造は使わないよ。順序木を構成して根から最小値を取り出すヒープソートの説明には当たらないよ。

選択肢エ（正解）

これは正解だよ。ヒープソートでは、未整列の部分を順序木（親の値が子の値以下になるヒープ）に構成し、根にある最小値を取り出して整列済の部分に移すよ。残りを再び順序木に整える操作を繰り返して未整列の部分を縮めていくから、この記述はヒープソートの説明として適切だよ。

学習のポイント

シェル・クイック・バブル・ヒープの各ソートの手順の特徴を、名前と対応付けて区別できるようにしよう。