Problem TSORT : Time Exceeds

general
21

Hey!
Now since i have used Quicksort technique why is it giving runtime error as “NULL POINTER ASSIGNMENT”.

There dosn’t seem anything wrong with this code.

#include<iostream>

using namespace std;

void Quicksort(int*,int,int);

int partition(int*,int,int);

void swap(int*,int*);

int main()

{

int n,i;

cin>>n;

int *arr=new int[n];

for(i=0;i<n;i++)

cin>>arr[i];

Quicksort(arr,0,n-1);

for(i=0;i<n;i++)

cout<<"\n"<<arr[i];

delete[] arr;

return 0;

}

void Quicksort(int *A,int beg,int end)

{

	int pindex;

	if(beg<end)

	{

                pindex=partition(A,beg,end);

                Quicksort(A,beg,pindex-1);

		Quicksort(A,pindex+1,end);

	}
}

int partition(int *A,int beg,int end)
{

               int pivot=A[end];

               int pindex=beg;
	       for(int i=beg;i<end;i++)
	      {

if(A[i]<=pivot)

		{

			swap(&A[i],&A[pindex]);

			pindex++;

		}
	}

	swap(&A[pindex],&A[end]);

	return pindex;

}

void swap(int *a,int *b)

{

	int temp;

	temp=*a;

	*a=*b;

	*b=temp;
}
22

please view my quicksort code in the bottom…

23

what should i do??

24

is still giving TLE in quicksort.

25

this is the basic quick sort. I mean the naive one! Check for the case when the array is reversely sorted. The time complexity will be O(n^2). So use randomized quick sort. You can even use inbuilt sort function which is implemented using quick sort-sort(arr,arr+n) is the syntax of this inbuilt function. Include algorithm header file

1 Like
26

@kaushik_iitd i implemented it using mergesort and it got AC. As i told -__- http://www.codechef.com/viewsolution/5236275

27

For people who think that mergesort and quicksort will give TLE for this question, it wont. Maybe u guys are getting tle because of a slow i/o method. Here’s my implementation of mergesort for AC. http://www.codechef.com/viewsolution/5236275

28

You can view above quicksort submitted by me…i dont think there is any slow i/o method and its still giving TLE.

29

Fine… let me check

30

inbuilt sort will work
you can use merge or heap sort also

1 Like
31

hey google and read about counting sort. It executes sorting in O(n) complexity or else merge sort or quick sort is best! :slight_smile:

32

use sort in stl and you are good to go

33

use sort in stl and you are good to go

34

Please accept an answer so that we can close this question.