# time exceed in turbo sort

#include<stdio.h>
//#include<conio.h>
int quiksort(int,int);
int partition(int,int);
//#include<malloc.h>
int a[1000001];
int main()
{
// int a[1000001];
long int i,t;
scanf("%ld",&t);
// a=(int*)malloc(t*sizeof(int));
for(i=0;i<t;i++)
scanf("%ld",&a[i]);

``````quiksort(0,t-1);
for(i=0;i<t;i++)
printf("%ld\n",a[i]);
``````

//getch();
return 0;
}

``````int quiksort(int i,int j)
{  int k;
if(i>=j)
return 0;
else
{k=partition(i,j);
quiksort(i,k);
quiksort(k+1,j);
}
return 0;
}
``````

int partition(int l ,int r)
{
int i=l,j=r,p,temp,m;

``````p=a[i];
while(i<j)
{ while(i<j&& (a[i]<p))i++;
while(i<j && (a[j]>=p))j--;
if(i<j)
{temp=a[i];
a[i]=a[j];
a[j]=temp;

}

}if(a[j]<=p)
return j;
else
return j-1;``````

first of all ur QuicSort is very inefficient .it will take quadratic time in no of elements in worst case.
only way to pass the tle use randomised QuickSort u can do it in a no of ways

1. use linear time KNUTH suffle to get random order fist
2. or just change the partitoning element from p=a[i] to p=a[(l+r)/2]
**BUT ** this also cannot gurantee to pass the tle if number of duplicate elements are in significant amount

tip->use dijkstra 3 way partinoning with randomised Quicksort this will reduce the running time from
O(nlogn) to ~O(n) if there are significant no of duplicate keys