×

# [closed] Problem TSORT : Time Exceeds

 0 Somebody help me in curing 'Time Limit' for this program! As else the code seems correct.... #include int main() { long long n,i,j,small,loc,temp; scanf("%lld",&n); long long *arr=new long long[n]; for(i=0;i<=n-1;i++) scanf("%lld",&arr[i]); for(i=0;i

### The question has been closed for the following reason "The question is answered" by kunal361 31 Oct '14, 21:42

 1 Bubble sort will ofcourse give you an error as n is large. Try a fast sorting algorithm like quicksort or mergesort! answered 24 Oct '14, 01:41 2.0k●2●14●32 accept rate: 20% 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. (25 Oct '14, 17:31)
 1 Even Quicksort and MergeSort would get TLE for this question. Count Sort is what you require :) answered 24 Oct '14, 01:52 1.6k●1●8●18 accept rate: 36% 1 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! (24 Oct '14, 03:48) and anyway the time limit of this function in 5 sec. One can blindly vouch for merge sort or quicksort for this case. (24 Oct '14, 03:51) Weak test cases probably. I'm sure you won't get AC here with the above implementations :P http://www.spoj.com/problems/TSORT/ (24 Oct '14, 04:13) i have already done it on SPOj as well -- and FYI, i got an AC! It works -- (24 Oct '14, 04:53) 2 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. (24 Oct '14, 04:55) My bad :) 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). (24 Oct '14, 18:14) 1 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. (24 Oct '14, 18:20) @kaushik_iitd i implemented it using mergesort and it got AC. As i told -__- http://www.codechef.com/viewsolution/5236275 (29 Oct '14, 17:41) showing 5 of 8 show all
 1 The solution is to use Counting Sort, O(n) time complexity answered 24 Oct '14, 18:31 4★ahmedtai 146●4 accept rate: 7%
 1 merge sort will work as it takesO(nlogn)in worst casees............ answered 25 Oct '14, 13:36 2★s10ky18 30●1●2 accept rate: 0%
 1 inbuilt sort will work you can use merge or heap sort also answered 30 Oct '14, 17:47 93●1●4 accept rate: 0%
 0 @wrangler00 Bro Check this discussion link.. http://discuss.codechef.com/questions/14768/turbo-sort?page=1#53514 User argonaut gave an amazing answer for tackling Turbo Sort problem. You may refer to my solution too, I have implemented the same logic in c (including fast input and output) after reading that discussion page Solution Link answered 25 Oct '14, 10:32 1.9k●1●12●43 accept rate: 14%
 0 @pranjalranjan 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. answered 25 Oct '14, 17:30 0●1●1●4 accept rate: 0% 1 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. (25 Oct '14, 18:24)
 0 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 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>arr[i]; Quicksort(arr,0,n-1); for(i=0;i
 0 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 answered 29 Oct '14, 17:42 2.0k●2●14●32 accept rate: 20% You can view above quicksort submitted by me.....i dont think there is any slow i/o method and its still giving TLE. (29 Oct '14, 17:55) Fine.. let me check (29 Oct '14, 17:58)
 0 hey google and read about counting sort. It executes sorting in O(n) complexity or else merge sort or quick sort is best! :) answered 30 Oct '14, 19:48 43●1●4●19 accept rate: 0%
 0 use sort in stl and you are good to go answered 31 Oct '14, 18:27 893●2●11●35 accept rate: 10%
 0 use sort in stl and you are good to go answered 31 Oct '14, 18:27 893●2●11●35 accept rate: 10%

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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:

question asked: 24 Oct '14, 01:31

question was seen: 1,148 times

last updated: 31 Oct '14, 21:42