基本情報技術者試験 過去問解説
クイックソートとは？基本情報技術者試験 平成30年度 秋期 午前 問6を解説
基本情報技術者試験 平成30年度 秋期 午前 問6は、クイックソートに関する理解を問う問題です。検索から入っても、問題文、選択肢、正解、解説、各選択肢がなぜ違うかをこのページだけで確認できます。
問題文
クイックソートの処理方法を説明したものはどれか。
この問題の出題ポイント
- クイックソートの定義だけでなく、問題文中の条件がどの選択肢に当てはまるかを確認する。
- アルゴリズム分野では、用語の目的・主体・責任範囲の違いが選択肢で問われやすい。
選択肢
- ア既に整列済みのデータ列の正しい位置に，データを追加する操作を繰り返していく方法である。
- イデータ中の最小値を求め，次にそれを除いた部分の中から最小値を求める。この操作を繰り返していく方法である。
- ウ適当な基準値を選び，それよりも小さな値のグループと大きな値のグループにデータを分割する。同様にして，グループの中で基準値を選び，それぞれのグループを分割する。この操作を繰り返していく方法である。正解
- エ隣り合ったデータの比較と入替えを繰り返すことによって，小さな値のデータを次第に端の方に移していく方法である。
正解
ウ: 適当な基準値を選び，それよりも小さな値のグループと大きな値のグループにデータを分割する。同様にして，グループの中で基準値を選び，それぞれのグループを分割する。この操作を繰り返していく方法である。
解説
クイックソートはピボット（基準値）を選び、それより小さいグループと大きいグループに分割し、各グループを再帰的に分割していく分割統治アルゴリズムです。ウが正解。
なぜ他の選択肢が違うのか
ア
整列済み列の正しい位置にデータを追加していくのは挿入ソートの説明です。
イ
最小値を選び続けるのは選択ソートの説明です。
ウ（正解）
ピボットで分割し再帰的に処理するクイックソートの定義そのものであり、正解です。
エ
隣り合うデータの比較・入替で次第に端へ移すのはバブルソートの説明です。
解き方の整理
クイックソートの問題では、選択肢のキーワードだけで判断せず、問題文が示す条件と正解選択肢の説明が一致しているかを見ます。誤答選択肢は、似た用語を混ぜる、主体を入れ替える、目的や範囲を広げすぎる、という形で作られることが多いため、選択肢別解説まで確認しておくと復習効率が上がります。
関連問題
前後の問題
平成30年度 秋期 午前 の関連する問題
復習を続ける
間違えた問題、苦手タグ、模試履歴を保存して復習する導線を用意しています。広告なしPro、弱点分析、復習リマインダーは段階的に提供予定です。