BFTRアルゴリズム(中位数の中位数アルゴリズム)はn個の数の中でk番目に大きい数を求めます

1362 ワード

BFTRアルゴリズムは、n個の数のうちk番目に大きい(すなわちn-1-k番目に小さい)数を求めるものであり、その考え方は、クイックソートにおいてPartionのpivot値を最適化することに基づいており、クイックソートにおける各クイック列のpivotの選択は、一般的に配列の先頭または末尾(数値比較がランダム)であり、BFTRは、毎回5分中位数の中位数をpivotとして次のクイックソートを行うものであり、これによりアルゴリズムの時間的複雑度を最悪のO(n^2)からO(n)に変えることができる.
実装コードは次のとおりです.
#include 
using namespace std;
const int maxn=1000;
int a[maxn],n,k; //  n      a  k ( n-1-k )  
void Insert_Sort(int a[],int l,int r)
{//    5  ,      
    for(int i=l;i<=r;i++)
    {
        int tmp=a[i],j=i-1;
        for(;j>=l&&tmp0)
{
Insert_Sort(a,i,i+res-1);
n=i-l;
swap(a[l+n/5],a[i+res/2]);
}
n/=5; //a[0..n] パケットの   を  する
if(n<=1) return a[l]; //   が2   (  きn<=1)の  は   さい
return Find_mid(a,l,l+n); //2つ  の  、   に   を し けます。
}
int Find_pos(int a[],int l,int r,int mid)
//   の   aの  きを つける
for(int i=l;i<=r;i++)
if(a[i]==mid) return i;
return -1;
}
int Partion(int a[],int l,int r,int pos)
//  プロセスを う
swap(a[pos],a[l]); // つかった   の   (すなわちmid)を  aの   に き える
int i=l,j=r;
int pivot=a[l];
while(i=pivot) j--;
a[i]=a[j];
while(ik) return BFPTR(a,l,i-1,k);
return BFPTR(a,i+1,r,k-m);
}
int main()
{
while(cin>>n)
{
for(int i=0;i>a[i];
cin>>k;
cout<