ランダム選択アルゴリズム---Randomized Selection Algorithm

Introduction
順序統計に関する多くの情報を見たことがあります.ソートしないで無秩序配列でK番目に小さい数を見つけたらどうしますか?
最大値を探す一般的な方法は、配列を巡る最大値変数を定義することです.しかし、2番目に大きい数値を探すにはどうすればいいのでしょうか.2つの変数が必要ですか?100番目に小さい数値を探していたら?
上記の問題を解決する方法は、次に紹介するランダム選択アルゴリズムであるRandomized Selection Algorithmです.
Concept
まずランダムに配列をpartitionして、ランダムな点の配列の中の位置を得て、それから配列の開始位置を減らして、これは探している配列の中のk-thの位置かもしれません
例:
配列:arr=9,5,7,1,10,2,3
ランダムに選択した中間点が5の場合、5に従ってpartitionを行います.結果は次のとおりです.
配列:arr=1 2 3 5 9 10
partitionの後に返される位置はpos=3(配列開始位置は0)なので、正確なk番目の位置の計算式は:
pos-start+1(posは戻る位置)
上記の式で計算した結果がkと等しければ,最適解が得られ,O(n)時間だけで見つかったことを示した.
しかし、私たちがランダムに選択することはできない点が私たちが探している数値なので、最初のpartitionの後にどうすればいいか分かりません.
次の手順に従います.
        1   2   3      5      9  7   10
      start          mid            end
現在k=mid-start+1=4
今、私たちは6番目の小さな数値が必要です.私たちの目で見れば7です.今、私たちは4番目の小さな数値を手に入れました.4<6である以上、6番目に小さいのは右側にあるはずです.
9 7 10側で
配列のこちらの開始位置はmid+1で、
しかし、6番目の小さい数値は、この半分の配列で(6〜4)番目の小さい数値であるべきである.だから私たちは再帰的に実現すれば見つけることができます.
原理はこれです.次はソースです.

#include <iostream>
#include <cstdlib>

using namespace std;

int random_partition(int* arr, int start, int end)
{
    int pivotIdx = start + rand() % (end-start+1);
    int pivot = arr[pivotIdx];
    swap(arr[pivotIdx], arr[end]); // move pivot element to the end
    pivotIdx = end;
    int i = start -1;

    for(int j=start; j<=end-1; j++)
    {
        if(arr[j] <= pivot)
        {
            i = i+1;
            swap(arr[i], arr[j]);
        }
    }

    swap(arr[i+1], arr[pivotIdx]);
    return i+1;
}

int random_selection(int* arr, int start, int end, int k)
{
    if(start == end)
        return arr[start];

    if(k ==0) return -1;

    if(start < end)
    {

        int mid = random_partition(arr, start, end);
        int i = mid - start + 1;
        if(i == k)
            return arr[mid];
        else if(k < i)
            return random_selection(arr, start, mid-1, k);
        else
            return random_selection(arr, mid+1, end, k-i);
    }

}
int main()
{
    int A[] = {9,5,7,1,10,2,3};
    int loc = random_selection(A, 0,6,5);
    cout << "the 5th smallest is  " << loc << endl;
    return 0;
}