平成23年度 特別 基本情報技術者試験 午前 問8
テクノロジ／アルゴリズム整列アルゴリズムの一つであるクイックソートの記述として，適切なものはどれか。
出典：平成23年度 特別 基本情報技術者試験 午前 問8
- ア対象集合から基準となる要素を選び，これよりも大きい要素の集合と小さい要素の集合に分割する。この操作を繰り返すことで，整列を行う。
- イ対象集合から最も小さい要素を順次取り出して，整列を行う。
- ウ対象集合から要素を順次取り出し，それまでに取り出した要素の集合に順序関係を保つよう挿入して，整列を行う。
- エ隣り合う要素を比較し，逆順であれば交換して，整列を行う。
正解：ア
解説
クイックソートは，対象集合から基準（ピボット）となる要素を選び，それより大きい要素の集合と小さい要素の集合に分割し，各集合に対して再帰的に同じ処理を繰り返すことで整列するアルゴリズムです。分割統治法の代表例であり，平均計算量はO(n log n)です。
選択肢ごとの解説
- ア正しい。基準要素で大小2つの集合に分割する操作を繰り返すのはクイックソートの説明です。
- イ誤り。最小要素を順次取り出して整列するのは選択ソートの説明です。
- ウ誤り。取り出した要素を既に整列済みの集合に順序を保って挿入していくのは挿入ソートの説明です。
- エ誤り。隣り合う要素を比較して逆順なら交換するのはバブルソートの説明です。