You are not logged in. Please login at www.codechef.com to post your questions!

×

BEGINNER HELP PLS. QUICKSORT TIME LIMIT EXCEEDED!!!!!

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

asked 21 Jul '17, 13:37

codesniper99's gravatar image

3★codesniper99
1186
accept rate: 7%


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.

link

answered 21 Jul '17, 13:53

vijju123's gravatar image

4★vijju123 ♦♦
15.2k11859
accept rate: 18%

edited 21 Jul '17, 14:02

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

Link to learn:-

Merge Sort

Randomized Quick Sort Sort

link

answered 26 Sep '17, 21:48

honeyyadav's gravatar image

2★honeyyadav
262
accept rate: 10%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×2,698
×1,600
×421
×19
×18

question asked: 21 Jul '17, 13:37

question was seen: 540 times

last updated: 26 Sep '17, 21:48