Problem TSORT : Time Exceeds

general
15

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
16

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

17

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

18

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

19

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
20

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).

21

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
22

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.

23

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
24

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

25

How do we accept an answer??

26

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

27

please view my quicksort code in the bottom…

28

what should i do??

29

is still giving TLE in quicksort.

30

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
31

@kaushik_iitd i implemented it using mergesort and it got AC. As i told -__- CodeChef: Practical coding for everyone

32

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

33

Fine… let me check

34

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