配列の分割（パーティション）手法でk番目に小さい要素を見つけるC++プログラム

本記事では、配列を分割（パーティション）する手法を用いて、配列内のk番目に小さい要素を求めるC++プログラムを解説します。この手法はクイックソートの考え方を応用したもので、配列全体をソートすることなく、目的の要素だけを効率的に特定できる点が特徴です。

アルゴリズム

まず、ピボットを基準に配列を分割する CreatePartition() 関数と、その結果をもとにk番目に小さい要素が存在する範囲を再帰的に絞り込む Partition() 関数を使用します。

Begin
    関数 CreatePartition() は 配列 a、下限 l、上限 h を引数にとる
    in := l、pi := h とする
    i を l から h の範囲で繰り返す
        もし a[i] < a[pi] ならば
            a[i] と a[in] の値を交換する
            in を 1 増やす
        繰り返し終了
    a[pi] と a[in] の値を交換する
    in を返す
End
Begin
    関数 Partition():
    引数:
        配列 A、下限 low、上限 high、および k
    関数の処理内容:
        もし low < high ならば
            p_in := Create_Partition(A, low, high)
            もし p_in = k-1 ならば
                k-1 を返す
            そうでなく p_in > k-1 ならば
                Partition(A, low, p_in – 1, k) を呼び出す
            それ以外の場合
                Partition(A, p_in + 1, high, k) を呼び出す
End

処理の流れのポイント

• CreatePartition()：末尾の要素をピボットとして扱い、ピボットより小さい要素を左側に集めます。最終的にピボットが正しい位置に配置され、そのインデックスを返します。
• Partition()：分割後のピボット位置 p_in と k-1 を比較し、一致すればその位置の要素がk番目に小さい要素です。p_in が大きければ左側の部分配列へ、小さければ右側の部分配列へ再帰的に探索範囲を狭めていきます。

サンプルコード

#include<iostream>
using namespace std;
void swap(int *a, int *b) {
    int t;
    t = *a;
    *a = *b;
    *b = t;
}
int CreatePartition(int a[], int l, int h) {
    int pi, in, i;
    in = l;
    pi = h;
    for(i=l; i < h; i++) {
        if(a[i] < a[pi]) {
            swap(&a[i], &a[in]);
            in++;
        }
    }
    swap(&a[pi], &a[in]);
    return in;
}
int Partition(int a[], int low, int high, int k) {
    int p_in;
    if(low < high) {
        p_in = CreatePartition(a, low, high);
        if(p_in == k-1)
            return k-1;
        else if(p_in > k-1)
            Partition(a, low, p_in-1, k);
        else
            Partition(a, p_in+1, high, k);
    }
}
int main() {
    int n, i, k, k_k;
    cout<<"\nEnter the number array elements: ";
    cin>>n;
    int a[n];
    for(i = 0; i < n; i++) {
        cout<<"Enter element "<<i+1<<": ";
        cin>>a[i];
    }
    cout<<"\nEnter the k for the kth smallest element: ";
    cin>>k;
    k_k = Partition(a, 0, n-1, k);
    cout<<"\nThe kth smallest element: "<<a[k_k];
    return 0;
}

コードの解説

swap() 関数はポインタを使って2つの整数値を入れ替える補助関数です。CreatePartition() はLomuto方式のパーティションを実装しており、Partition() はクイックセレクトと呼ばれる手法で再帰的に探索を行います。これにより、平均計算量はO(n)となり、配列全体をソートするO(n log n)よりも高速にk番目の要素を求められます。

実行結果

Enter the number array elements: 4
Enter element 1: 3
Enter element 2: 2
Enter element 3: 5
Enter element 4: 4
Enter the k for the kth smallest element: 3
The kth smallest element: 4

この実行例では、配列 {3, 2, 5, 4} の中から3番目に小さい要素を求めた結果、「4」が出力されています。ソート済みの順序は {2, 3, 4, 5} となるため、3番目の要素が4であることが確認できます。