平成21年度 秋期 基本情報技術者試験 午前 問6
テクノロジ／アルゴリズムクイックソートの処理方法を説明したものはどれか。
出典：平成21年度 秋期 基本情報技術者試験 午前 問6
- ア既に整列済みのデータ列の正しい位置に，データを追加する操作を繰り返していく方法である。
- イデータ中の最小値を求め，次にそれを除いた部分の中から最小値を求める。この操作を繰り返していく方法である。
- ウ適当な基準値を選び，それより小さな値のグループと大きな値のグループにデータを分割する。同様にして，グループの中で基準値を選び，それぞれのグループを分割する。この操作を繰り返していく方法である。
- エ隣り合ったデータの比較と入替えを繰り返すことによって，小さな値のデータを次第に端の方に移していく方法である。
正解：ウ
解説
クイックソートは，適当な基準値（ピボット）を選び，それより小さい値のグループと大きい値のグループにデータを分割し，各グループの中でも同様に基準値を選んで再帰的に分割していく方法です。平均的な計算量は O(n log n) であり，代表的な高速ソートアルゴリズムの一つです。
選択肢ごとの解説
- ア誤り。整列済みの列に順にデータを挿入していくのは挿入ソートの説明です。
- イ誤り。最小値を探して順に確定していくのは選択ソートの説明です。
- ウ正しい。基準値でグループを分割し，各グループで再帰的に同じ操作を繰り返すのがクイックソートの処理方法です。
- エ誤り。隣り合うデータの比較と入替えを繰り返すのはバブルソートの説明です。