Пожалуйста, подпишитесь на официальный канал Codeforces в Telegram по ссылке https://t.me/codeforces_official. ×

Блог пользователя CazadorDivino

Sort array of int vs Sort array of Integer
Автор CazadorDivino, 9 лет назад, По-английски

Why Arrays.sort(Integer) is more fast that Arrays.sort(int) ?(JAVA)

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
9 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Because of antiquicksort tests. You can random-shuffle your array before sorting and everything will be fine

→ Ответить
  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    As I can do random-shuffle, could you tell me more about what it means to do that. Because as I understand it has to do with the algorithms using JAVA to order according to data type.

    → Ответить
    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Let's say that you are given a random permutation of ints from 1, 2, ..., n. If you sort them with Arrays.sort then you are almost completely sure that it will be , that means that the probability of hitting a permutation that causes O(n2) is so low that is negligible. Furthermore, it will be faster than using a Mergesort (because Quicksort is almost always faster than Mergesort).

      However, if the input is not a random permutation, then whoever made that input could have been "malicious" and tuned the order of the numbers in order to cause O(n2) behavior. If you use random shuffle, then you're back in the case no matter what original order the input had.

      See dalex's post if you want to see how to generate a "malicious" input.

      → Ответить
»
9 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

The main reason is that Java uses two different sorting algorithms in the cases you mentioned.

In the Arrays.sort(int) (or other primitive types) case, Java uses Quicksort, which has a O(n2) worst case. Instead, in the Arrays.sort(Object) case, it uses Mergesort, which has a worst case.

Why? Check out the answer here.

→ Ответить
»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

on average sample, sort(int) is much faster (because it works with primitives), but it has O(N^2) worstcase because it's plain quicksort, and in certain CF problems other users might use it to hack solution. sort(Integer) is mergesort and while it's slower, its worstcase is still O(N*log N)

→ Ответить