クイックソートを応用した選択アルゴリズム
平成27年度 春期 基本情報技術者試験に出題された「クイックソートを応用した選択アルゴリズム」を MATLAB で作成しました。
クイックソートとは
クイックソート(quicksort)は,1960 年にアントニー・ホーアが開発したソートのアルゴリズム。分割統治法の一種。
n 個のデータをソートする際の最良計算量及び平均計算量は, O(n log n) である。
他のソート法と比べて,一般的に最も高速だといわれているが対象のデータの並びやデータ数によっては必ずしも速いわけではなく,最悪の計算量は O(n2) である。
選択アルゴリズムの概要
与えられた n 個のデータの中から k 番目に小さい値を選択する方法として,クイックソートを応用したアルゴリズムを考える。
クイックソートとは,n 個のデータをある基準値以下の値のグループと基準値以上の値のグループに分割し(基準値はどちらのグループに入れても構わらない),更にそれぞれのグループで基準値を選んで二つのグループに分割するという処理を繰り返してデータを整列するアルゴリズムである。
クイックソートを応用して k 番目に小さい値を選択するアルゴリズムでは,データを二つのグループに分割した時点で,求める値はどちらのグループに含まれるかが確定するので,そのグループだけに,更に分割する処理を繰り返し適用する。
グループの分割ができなくなった時点で,k 番目に小さい値が選択されている。
MATLAB で作成した選択アルゴリズム
クイックソートを応用した選択アルゴリズムを MATLAB で作成しました。
引数,返却値の仕様は次表のとおりです。
引数名/返却値 | データ型 | 出力/入力 | 意味 |
---|---|---|---|
x[] | 整数型 | 入力 | 数値が格納されている一次元配列 |
n | 整数型 | 入力 | 数値の個数 |
k | 整数型 | 入力 | 選択する数値の小ささの順位を示す値 |
返却値 x(1,k) | 整数型 | 出力 | 出力された数値 |
MATLAB のコードを以下に示します。
x = [3, 5, 1, 4, 2, 7, 6];
n = length(x);
k = 3;
Top = 1;
Last = n;
while Top < Last
Pivot = x(k);
i = Top;
j = Last;
while i <= j
while x(i) < Pivot
i = i + 1;
end
while x(j) > Pivot
j = j - 1;
end
if i >= j
break;
end
% Swap elements
temp = x(i);
x(i) = x(j);
x(j) = temp;
i = i + 1;
j = j - 1;
end
if i - 1 <= k
Top = i;
end
if j + 1 >= k
Last = j;
end
end
disp(x(k));
上記の MALAB コードを実行した結果は「3」である。