Problem TSORT : Time Exceeds

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

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. CodeChef: Practical coding for everyone

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

1 Like

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:

use sort in stl and you are good to go

use sort in stl and you are good to go

Nope. quicksort won’t. Not mergesort as well, if implemented properly. I used the sort function from the algorithm library which uses the quicksort algorithm for large n and nope, it didn’t give TLE. Dont worry it’ll work!

1 Like

and anyway the time limit of this function in 5 sec. One can blindly vouch for merge sort or quicksort for this case.

Weak test cases probably. I’m sure you won’t get AC here with the above implementations :stuck_out_tongue: SPOJ.com - Problem TSORT

i have already done it on SPOj as well -- and FYI, i got an AC! It works --

Standard Sorting(C++) - 2.39 s
Merge Sort - 3.11 s
Heap Sort - 3.10 s
Count Sort - 2.33 s
Results posted by someone on comments of the same problem on SPOJ.

2 Likes

My bad :slight_smile: Anyway can I see your implementation of Standard sort which was AC on Spoj? What’s the point of solving the question then if you solve with any sorting algorithm (n log n).

Inbuilt Quick Sort in c can get you AC.
Heap sort is also working .
Counting sort is also one option with O(n).
Happy coding.

1 Like

Its right that bubble sort uses too much time for execution.

BUT many have submitted using this sort technique successfully so whats the problem with my code.

Nobody would have used bubble sort, i am sure! If u feel that someone has used bubble sort and still submitted successfully, please comment a link of the solution! Bubble sort can never solve this problem. You atleast require an O(nlogn) technique.

1 Like

bro! If you understood please do accept the answer so that we can close the question :slight_smile:

How do we accept an answer??

There will be a tick symbol down to the vote down symbol.

please view my quicksort code in the bottom…

what should i do??