令和3年度秋期 データベーススペシャリスト 午前Ⅰ 問3

整列処理を読むための一つの視点

各選択肢を覚えた特徴と照合するのではなく、処理が進む途中でデータのどの部分が扱われ、どの時点で状態が変わるのかに注目して、説明の前提と結論の対応を丁寧に確認しましょう。

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

確認する観点は、処理の各段階で「すでに位置や状態が決まった部分」と「これから比較や操作の対象になる部分」を区別できるかです。全体の印象ではなく、段階ごとの変化を追ってください。

視点

整列を学ぶときは、入力の並びを一度に評価せず、処理を段階に分けて観察します。各段階で対象範囲がどう変わるか、保持される条件が何かを言葉で整理すると、説明の読み違いを減らせます。

確認ポイント

• 処理の開始時点と各段階の対象範囲を区別できているか
• 一つの操作の前後で、並びの状態がどう変化したと説明されているか
• 説明が前提・途中経過・結果のどこを述べているかを確認したか

正解

ウ

解説

バブルソートは、隣り合う要素を順番に比較し、大小関係が逆なら交換する処理を繰り返して整列するアルゴリズムです。

理由

バブルソートでは、隣り合う要素を比較し、並ぶ順序が逆になっている場合に交換する。この局所的な比較と交換を繰り返すことで、要素を目的の順序へ移動させていく。したがって、該当する説明はウです。

比較

アは一定間隔の部分列を整列して間隔を狭めるシェルソート、イは基準値で要素を分けて再帰的に処理するクイックソート、エは順序木から最小値を取り出すヒープソートの説明です。いずれもバブルソートの操作ではありません。

選択肢ア

これは不正解だよ。一定の間隔をおいて要素を取り出した部分列を整列し、その間隔を徐々に狭めていく方法はシェルソートの説明である。バブルソートは部分列の間隔を変えて処理するのではなく、隣接要素の比較と交換を基本操作とするため、この説明とは一致しない。

選択肢イ

これは不正解だよ。基準値より大きい要素と小さい要素に分け、それぞれの区分を同様に処理する方法はクイックソートの説明である。バブルソートには基準値を使って要素を区分する操作はなく、比較対象を分割して処理する方式でもない。

選択肢ウ（正解）

これは正解だよ。バブルソートは、隣り合う要素を比較し、大小関係が逆になっているときにその二つを交換する操作を繰り返す。選択肢はこの基本的な処理をそのまま説明しており、バブルソートの特徴と一致している。

選択肢エ

これは不正解だよ。未整列部分を順序木として扱い、そこから最小値を取り出して整列済み部分へ移す方法はヒープソートの説明である。バブルソートは順序木を構成したり最小値を木から取り出したりせず、隣接要素の比較と交換によって整列する。

学習のポイント

バブルソートと、間隔・基準値・木構造を使う整列法との違いを理解する。