クイックソートを応用した選択アルゴリズム

平成27年度 春期 基本情報技術者試験に出題された「クイックソートを応用した選択アルゴリズム」を MATLAB で作成しました。

クイックソートとは

クイックソート（quicksort）は，1960 年にアントニー・ホーアが開発したソートのアルゴリズム。分割統治法の一種。

n 個のデータをソートする際の最良計算量及び平均計算量は， O(n log n) である。

他のソート法と比べて，一般的に最も高速だといわれているが対象のデータの並びやデータ数によっては必ずしも速いわけではなく，最悪の計算量は O(n²) である。

選択アルゴリズムの概要

与えられた 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」である。