I was solving http://www.codechef.com/problems/CD1IT1
I am using the following method of quickselect for kth order statistics. It was giving TLE while the normal sorting and returning the middle element got AC. Is’nt quick select supposed to be faster
#include <iostream>
using namespace std;
long long int swap(long long int &a,long long int &b)
{
long long temp=a;
a=b;
b=temp;
}
long long partition(long long arr[],int lo,int hi,int k)
{
long long pivot=arr[lo];
int i=lo+1;
int j=hi;
while(i<=j)
{
while(arr[i]<pivot && i!=hi)
i++;
while(arr[j]>pivot)
j--;
if(i<j)
{
swap(arr[i],arr[j]);
i++;
j--;
}
else
break;
}
swap(arr[j],arr[lo]);
if((j-lo+1)==k)
return arr[j];
else if((j-lo+1)<k)
return partition(arr,j+1,hi,k-(j-lo+1));
else
return partition(arr,lo,j-1,k);
}
int main()
{
long long n,*arr;
scanf("%lld",&n);
arr=new long long[n];
for(int i=0;i<n;i++)
scanf("%lld",&arr[i]);
long long k;
if(n%2==0)
k=n/2;
else
k=(n+1)/2;
printf("%lld",partition(arr,0,n-1,k));
return 0;
}