Beginner help pls. quicksort time limit exceeded!

help
, , , ,
1

HEY THERE ! I’m having problem when I submit my code for TurboSort Problem Code: TSORT

I’m using quicksort for it but somehow I get a Time Limit exceeded answer

Please help I’ve been stuck for a long time on this !!!
HELP A BEGINNER

#include <iostream>
#include<vector>
#include<stdlib.h>
#include<cstdio>
using namespace std;
 
long int  partition(vector<long int> &a,long int  l,long int  r)
{
    long int  i,j,x;
    long int  pivot;
 
    pivot=a[l];
    i=l+1;
    j=l+1;
    for(j=l+1;j<=r;j++)
       {
           if(a[j] < pivot)
           {
              x=a[i];
              a[i]=a[j];
              a[j]=x;
              i++;
           }
 
 
       }
    x=a[i-1];
    a[i-1]=a[l];
    a[l]=x;
 
    return i-1;
}
 
void qsort(vector<long int> &a,long int  l,long int  r)
  {   if(l<r)
     {
 
 
      long int  x= partition(a,l,r);
      qsort( a,l,x-1);
      qsort(a,x+1,r);
 
     }
  }

Thanks.

int  main()
{
    long int  n;
 
    scanf("%ld",&n);
    vector <long int> a(n);
 
    for(long int  i=0;i <n;i++)
     scanf("%ld",&a[i]);
 
 
    qsort(a,0,n-1);
 
 
     for(long int k=0;k<n;k++)
     printf("%ld\n",a[k]);
    return 0;
}
2

Quick sort can be O(N^2) in worst case which will give you a TLE.

You can simply use inbuilt sort function of C++ to get AC. The in built sort function is always O(NlogN) and uses many factors like recursion depth etc to determine how it should proceed further.

Its used like sort(arr,arr+n) . Google and learn more about it, this function is going to save you lot of TLEs later on.

3

Hey please use merge sort. Or use a randomized version of quick sort.

Link to learn:-

Merge Sort

Randomized Quick Sort Sort