In the problem Div 2 C of the recent Codeforces round #415, I got TLE on test 69. I was unable to figure out the reason as the loop was running for just n times. So, I changed my array to arraylist, and used Collections.sort()
instead of the Arrays.sort()
. To my surprise, it passed without any other changes! What could be the reason here? Check my last 2 submissions for this : TLE Submission and Accepted submission
Collections.sort()
usesTimsort
whileArrays.sort()
usesQuicksort
.Note:
Arrays.sort()
usesTimsort
onObject[]
.I tried to hack one solution that uses Java 8's Arrays.sort() in my room on that problem, using dalex's generator code from http://codeforces.net/blog/entry/4827, but it still ran in time. The generator advertises that it works on Java 7 though. Is there any difference between Java 7's and Java 8's Arrays.sort()? Is dalex's code obsolete somehow?
Note: the said solution got TLE in systest.
The code is 5 years old. There are other quicksort killers out there.
Arrays.sort()
is still usingQuicksort
for sorting arrays of primitives.Could you suggest any that are targeted to Java 8? A google search failed to come up with any.
After some research, I am not sure that it's possible to beat the current version of
Quicksort
. It still performs worse thanTimsort
but it will probably pass if the time limit is not that strict (i.e. for more than 200.000 elements, 2sec might not be enough).Declaring the array this way
Integer x[] = new Integer[n]; will solve the problem of time complexity .
This is an awful solution (at least for competitive programming). You are not sorting primitives but objects; autoboxing/unboxing will probably kill you in a time-sensitive problem.
Sorry, didn`t understand what you are trying to say. Can you please elaborate it properly?
As far as I know, I asked this doubt quite some time back and a few Java programmers told me to follow this policy.
Integer[]
is not the same asint[]
. One is an array of primitives and the other one is of objects. Java has a mechanism of converting fromInteger
toint
and vice-versa (autoboxin/unboxing) and it is not cheap. Everything will be much faster on primitives and not their wrapper classes.This is a solution to avoid sorting using
Quicksort
on arrays of primitives. But it is a bad one.A good solution would be to write your one sorting function for arrays of primitives or to use
Collections.sort
on some list-like class (i.e.ArrayList
) and to be prepared for a potential TLE.So you suggest using arraylist to solve this problem? I think that approach also has some downsides since the elements aren't together in memory, and it still has the same problem of wrapping and unwrapping Integer objects. As far as I know there are three workaround to the problem:
-use Integer[] arr instead of int[] arr.
-use ArrayList
-use int[] arr, but do a random shuffle on the elements before sorting.
Personaly, I don't think using Integer[] instead of int[] is such a big problem.
Please read what I said!.
I said that the best approach would be writing your own function. If you are not willing to do that, you can easily use
ArrayList
orInteger[]
' without knowing that it will pass the TL.If you really believe that using
Integer[]
instead ofint[]
is a solution to avoid strict time limits then I suggest you start doing that!