Beginner pls help quicksort time limit exceded!

help
, , , , , , ,
1

Problem Code : TSORT

Guys, I tried Quick Sort But to no Avail as a clock appears and tells me that my time limit is exceeded
… Hopefully code is neat

Please give any tips to quicken my Code

Please don’t judge I’m a Beginner :smiley:

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

     }
  }






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

@codesniper99 in your code one thing is that base condition is missing in recursion in the qsort function. You should call this function only when l<=r. Try this.
EDIT: I didn’t see that c_utkarsh has already answered the question very well. That one is perfect.

3

There are a few things wrong in the above code.

(1.) The data type for vector a is long long int but you have used “%d” specifier for taking input. So, change it to “%lld” in the for loop where you take input for the vector a.

(2.) You don’t have a condition to end the recursive function qsort(). Add this line in that function.

if(l >= r)
    break;

(3.) In the for loop in the function partition(), j should go upto r. So the condition should be j <= r instead of j < r.

(4.) After the for loop int the function partition(), you are not doing swapping properly. It should be

a[l] = x;

instead of

a[l] = a[i-1];

After doing these changes, your code should work fine.

4

Bro, I did the changes did not work! The code works but still the time is exceeded…

Pls help.