time exceed in turbo sort

general
, , ,
1

#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;
2

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