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<