How should I implement Sort properly if I have to use it without getting TLE?

general
1

I stumbled upon the problem of Chef and Integers (INTEG Problem - CodeChef), and thought I’ll give it a try. Now, the algorithm I’ve implemented uses sort. Now this obviously leads to a TLE for large input cases surely but is working otherwise. How should I implement sort to take care of this?

Or the only option there is, is to implement a different algorithm? How should that go about?

2

@razordude1717 : You are using quicksort which is O(n^2) in worst case . You should use some n log n algorithm for sorting , like merge sort or heap sort .

3

@razordude1717 >> You can use the C++ std::sort() or std::stable_sort(). That would save your time writing the code snippet to sort in your own code. std::sort() is a kind of hybrid algorithm. More details here

Example:

a[5] = {3, 7, 1, 2, 8};    //a sample array
std::sort(a, a+5);         //you can omit the "std::" part if you have already
                           //declared using namespace std

Output will be a sorted array.

4

@vineetpaliwal: I tried heap sort too, it still is causing TLE. I think it has to do with the algorithm.

5

@@razordude1717 : You are actually simulating the whole process which will obviously give TLE . You have numbers in the range of -10^9 to 10^9 .

To see the correct algorithm please refer the editorial ,

http://discuss.codechef.com/questions/23733/integ-editorial

That should help you . If it is unclear to you , you can ask me here on this thread by tagging your query with @vineetpaliwal

6

TLE in INTEG is not because of sorting (i suppose you are using some nlog(n) algorithm).
After sorting you are supposed to use some tricky stuffs to reduce time complexity.
I used O(n) after sorting.
You can go through my solution
[Solution][1]
[1]: CodeChef: Practical coding for everyone

Ask me on this thread if you have any further queries.