応用情報技術者 2014年 秋期 午前2 問06
問題文
データ列が整列の過程で図のように上から下に推移する整列方法はどれか。ここで、図中のデータ列中の縦の区切り線は、その左右でデータ列が分割されていることを示す。
選択肢
ア：クイックソート
イ：シェルソート
ウ：ヒープソート
エ：マージソート（正解）
データ列が整列の過程で図のように上から下に推移する整列方法はどれか【午前2 解説】
要点まとめ
- 結論：図の整列過程は分割と統合を繰り返すマージソートの特徴を示しているため、正解はエ: マージソートです。
- 根拠：図中の縦の区切り線はデータ列の分割を表し、段ごとに部分列が整列されていく様子はマージソートの典型的な動作です。
- 差がつくポイント：クイックソートは分割はするが統合過程を明示しない、シェルソートはギャップを縮小しながら部分的に整列、ヒープソートはヒープ構造を用いるため図の分割表示とは異なります。
正解の理由
マージソートは「分割→整列→統合」を繰り返す安定な整列アルゴリズムです。図の各段が部分列に分割され、それらが整列されてから次の段で統合されている様子は、まさにマージソートの処理過程を表しています。
一方、クイックソートは分割はしますが、統合の過程を図示しません。シェルソートはギャップを用いた部分整列であり、ヒープソートはヒープ構造の操作が中心で分割表示はされません。したがって、図の特徴に最も合致するのはマージソートです。
一方、クイックソートは分割はしますが、統合の過程を図示しません。シェルソートはギャップを用いた部分整列であり、ヒープソートはヒープ構造の操作が中心で分割表示はされません。したがって、図の特徴に最も合致するのはマージソートです。
よくある誤解
クイックソートも分割を行うため、分割線がある図を見てクイックソートと誤認しやすいです。
また、シェルソートの部分整列と混同してしまうこともありますが、分割と統合の明示的な段階がない点で異なります。
また、シェルソートの部分整列と混同してしまうこともありますが、分割と統合の明示的な段階がない点で異なります。
解法ステップ
- 図の縦の区切り線が何を示すか確認する（部分列の分割）。
- 各段のデータ列の変化を観察し、部分列が整列されているかを確認。
- 分割された部分列が次の段で統合されているかをチェック。
- 分割→整列→統合の特徴を持つアルゴリズムを選択肢から特定。
- クイックソート、シェルソート、ヒープソートの特徴と比較し、最も合致するものを選ぶ。
選択肢別の誤答解説
- ア: クイックソート
分割はするが、統合過程を図示しないため、図の段階的な統合とは異なる。 - イ: シェルソート
ギャップを用いた部分整列であり、分割線や段階的統合の表現はない。 - ウ: ヒープソート
ヒープ構造の構築と削除操作が中心で、分割線による部分列の分割表示はない。 - エ: マージソート
分割と統合を繰り返す過程が図に一致し、正解。
補足コラム
マージソートは安定な整列アルゴリズムで、計算量は常にです。分割した部分列を再帰的に整列し、最後にマージ（統合）するため、分割と統合の過程が明確に分かれています。大規模データの外部ソートにも適用されることが多いです。
FAQ
Q: クイックソートとマージソートの違いは何ですか？
A: クイックソートは分割してピボットを基準に並べ替え、統合は不要ですが、マージソートは分割後に整列済み部分列を統合（マージ）します。
A: クイックソートは分割してピボットを基準に並べ替え、統合は不要ですが、マージソートは分割後に整列済み部分列を統合（マージ）します。
Q: シェルソートはどのような特徴がありますか？
A: シェルソートはギャップを徐々に縮小しながら部分的に整列を繰り返すアルゴリズムで、分割や統合の過程は明示されません。
A: シェルソートはギャップを徐々に縮小しながら部分的に整列を繰り返すアルゴリズムで、分割や統合の過程は明示されません。
関連キーワード: マージソート、分割統治法、安定ソート、ソートアルゴリズム、クイックソート、シェルソート、ヒープソート
\ せっかくなら /
応用情報技術者を
クイズ形式で学習しませんか？
クイズ画面へ遷移する→
すぐに利用可能！