検索問題整理(2)K番目に大きい数Kth Order Statisticを検索

高速ソートの考え方によって、Kth Order Statistic、すなわち、ソートされていない配列を与え、配列中のK番目に大きい数を見つける検索アルゴリズムを実現することができる.
このKth Order StatisticとtopKアルゴリズムには違いがあることに注意してください.TopKアルゴリズムは前Kの大きい数を見つけて、Kの数を探します.一方、Kth Order StatisticはK番目に大きい数を見つけて、1つの数だけ探します.

//        partition  
int partition_kth(int* arr, int st, int ed){
    int j=st;
    int i=j-1;
    int pivot=arr[ed];
    int temp;
    while (j<=ed-1) {
        if (pivot>arr[j]) {
            i++;
            temp=arr[i];
            arr[i]=arr[j];
            arr[j]=temp;
        }
        j++;
    }

    i++;
    temp=arr[ed];
    arr[ed]=arr[i];
    arr[i]=temp;
    return i;
}

関数の主なアルゴリズムは以下の通りで,再帰的な考え方を用いた.

//Kth Order Statistic  
int kth_order_statistic(int* arr, int st, int ed, int order)
{
    int attemp_order =  partition_kth(arr,st,ed);
    int temp1 =  attemp_order -st+1;
    if (temp1  == order)
        return arr[attemp_order];
    else if ( temp1 < order)
        kth_order_statistic(arr, attemp_order+1, ed, order-temp1);
    //NOTE1:   kth_order_statistic(arr, attemp_order+1, ed, order);
    //NOTE2:Kth Order           ，        。
    else
        kth_order_statistic(arr, st, attemp_order-1, order);
}

main関数は次のとおりです.

int main()
{
int unsorted_arr[10]={10,7,9,6,8,4,11,15,1,5};
    std::cout<<kth_order_statistic(unsorted_arr,0,9,1)<<std::endl;
    std::cout<<kth_order_statistic(unsorted_arr,0,9,7)<<std::endl;
    std::cout<<kth_order_statistic(unsorted_arr,0,9,9)<<std::endl;
return 0;
}

は、結果が配列の1番目、7番目、9番目に大きい数を返します.