# TLE: finding median using quickselect for kth order statistics

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;
}``````

Before asking such questions you should try to make an effort in finding out the time complexities of various algorithms.

The time limit is 1 second and a program can do computations roughly about the order of O(10^7).

I am sorry to say I have not completely read your code but I can assure you that quick sort is definitely not the fastest sorting algorithm. In case all the elements are already sorted or if they are in reverse order, quick sort will take a complexity of O(n^2). (Get a better understanding from this link http://geeksquiz.com/quick-sort/ ).
In the above question n has a maximum value of 10^5 and n^2 will be 10^10. (1 second will definitely be exceeded)

If you are looking for more optimum sorting algorithms you can refer merge sort (http://geeksquiz.com/merge-sort/) and heap sort (http://geeksquiz.com/heap-sort/)

For coding faster you can use the algorithm library available in C++ (http://www.cplusplus.com/reference/algorithm/sort/?kw=sort) which has a maximum time complexity of O(N*log2(N)).