クイックソートの特徴
クイックソートの説明として、適切なものはどれか。
- A
隣り合う要素を比較し、大小が逆であれば交換する処理を、交換が起きなくなるまで繰り返す。
- B
データを細かく分割して整列済みの部分列を作り、それらを順に併合して全体を整列する。
- C
未整列部分から最小値を探し、未整列部分の先頭の要素と交換する処理を繰り返す。
- D
基準値を選び、それより小さい要素の群と大きい要素の群に分ける処理を、各群に再帰的に繰り返す。
正解と解説を見る
正解:D
クイックソートは基準値(ピボット)で分割する方法を再帰的に繰り返す。マージソートは併合、バブルソートは隣接交換、選択ソートは最小値の選択で整列する。
- A
誤り。バブルソート(交換法)の説明である。
- B
誤り。マージソート(併合整列)の説明である。分割と併合で整列するので、基準値による分割とは異なる。
- C
誤り。選択ソート(基本選択法)の説明である。
- D
正しい。基準値(ピボット)による分割を繰り返すのがクイックソートである。平均計算量はO(n log n)、最悪はO(n^2)になる。
このサイトの問題は、公開されている出題範囲に沿って作ったオリジナルの模擬問題です。本試験の問題ではありません。独立行政法人情報処理推進機構(IPA)の公式サービスではありません。