クイックソート
くいっくそーと
定義
基準値(ピボット)で大小に分割し再帰的に並べる高速な整列アルゴリズム。
詳細解説
基準値ピボットを選び、それより小さい値と大きい値に分割(パーティション分割)、分割された部分にも同じ処理を再帰的に適用する分割統治法のアルゴリズム。平均計算量O(n log n)で、実用上最も高速なソートの一つ。最悪計算量はO(n²)だがピボット選択を工夫すれば回避できる。標準ライブラリのソート関数の内部で広く採用されている。
「クイックソート」が出る問題
RNN(Recurrent Neural Network:再帰型ニューラルネットワーク)の特徴として、最も適切なものはどれか。
見る人に意図が伝わりやすいデザインにするための四つの原則に関する次の記述中のa、bに入れる字句の適切な組合せはどれか。 [四つの原則] 近接:互いに関連する要素は近づけてグループにする。 [a]:要素を意図したルールに基づき配置する。 反復:要素ごとにデザインルールを繰り返す。 [b]:要素ごとの大小や強弱などの違いを明確にする。 組合せ: ア a=整列 b=価値 イ a=整列 b=対比 ウ a=操作 b=価値 エ a=操作 b=対比
4個の要素から成るデータの並びを、次の手順を繰り返して昇順に整列するとき、整列が終了するまでに(1)から(3)の一連の手順は、何回実行されるか。ここで、最初はデータの並び全体を整列対象とする。データの並び:[27, 42, 33, 12] 〔手順〕(1)整列対象中の要素の最大の値を選び、最後の要素と入れ替える。(2)最後の要素を整列対象から外す。(3)整列対象に要素が1個以上残っていれば、(1)から(3)の一連の手順を実行する。残っていなければ、整列完了なので終了する。
関連用語
よくある質問
Q. クイックソートとは何ですか?
A. 基準値(ピボット)で大小に分割し再帰的に並べる高速な整列アルゴリズム。
Q. IT パスポート試験での位置づけは?
A. テクノロジ系の重要用語です。出題頻度は 2/3 (★2)。 中程度の頻度で出題されます。