Flatfoot's blog

By Flatfoot, 6 years ago, In English,

Abstract

Below I will describe how to avoid TLE (timelimit exceeded) when sorting an array in Java. I will describe two methods.

Introduction

When trying to sort an array in Java it is convenient to use Arrays.sort():

long[] arr = {5,3,4,2,1};
Arrays.sort(arr);
// after sorting print arr

However, this method uses quicksort if the array contains elements of primitive datatype such as long or int. Quicksort has on average a runtime of , but keep in mind that the worst-case runtime is O(n2) for arrays that are almost sorted. As a consequence you can get a TLE (timelmit exceeded) by the online judge. Below are two methods that avoid this issue.

Method 1: Use objects (wrapper class)

We will use the wrapper class Long of the primitive datatype long. Given an array long[] arr we will introdue an array Long[] arr_obj. While long[] arr is sorted with quicksort Long[] arr_obj is sorted with mergesort which has a worst-case runtime of . In Java an array with objects is sorted with mergesort when using Arrays.sort().

long[] arr = {5,3,4,2,1};
int n = arr.length;
Long[] arr_obj = new Long[n];
for(int i=0; i<n; ++i){
   arr_obj[i] = new Long(arr[i]);
}
Arrays.sort(arr_obj);
// after sorting print arr_obj

Method 2: shuffling the array before quicksort

We can still use quicksort but in order to avoid the worst-case runtime of O(n2) for an almost sorted array we will first shuffle it and then apply quicksort.

long[] arr = {1,2,3,5,4};
shuffleArray(arr);
Arrays.sort(arr);
// after sorting print arr

The function shuffleArray() is given by

void shuffleArray(long[] arr){
        int n = arr.length;
        Random rnd = new Random();
        for(int i=0; i<n; ++i){
            long tmp = arr[i];
            int randomPos = i + rnd.nextInt(n-i);
            arr[i] = arr[randomPos];
            arr[randomPos] = tmp;
        }   
}

References

[1] [More On Shuffling An Array Correctly](http://blog.ryanrampersad.com/2012/03/more-on-shuffling-an-array-correctly/) – blog post by Ryan Rampersad.

[2] [Why java Arrays use two different sort algorithms for different types?](http://stackoverflow.com/questions/3707190/why-java-arrays-use-two-different-sort-algorithms-for-different-types) (discussion on stackoverflow.com)

[3] Java doc on [quicksort](http://docs.oracle.com/javase/7/docs/api/java/util/Arrays.html#sort(long[])) and [mergesort](http://docs.oracle.com/javase/7/docs/api/java/util/Arrays.html#sort(java.lang.Object[])).

 
 
 
 
  • Vote: I like it  
  • +31
  • Vote: I do not like it  

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone by the way explain why C++ std::sort in work fast?
Does it use randomized pivot during sorting?
Can I generate a test where std::sort gets TL?

  • »
    »
    6 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    In C++ std::sort() has worst case performance, so it's not possible to find an input that would reduce it to O(n2) running time like in Java's case. In GNU C++ in particular, the std::sort() function is implemented as Introsort.

    • »
      »
      »
      6 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Thanks for your answer, but there one thing that startles me — the Quicksort idea is always O(n2) worst case unless we use random pivot, isn't it?
      BTW, what is implemented as std::sort in MS Visual C++?

      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Actually, Quicksort has O(n2) worst case performance even if you choose the pivot randomly. It's just that the probability of this happening is almost zero, and no "bad" test can be prepared in advance. But if you are extremely unlucky, you could hit a O(n2) run time even with a random pivot or shuffle.

        As for MS C++, I don't know, but it still must have worst case performance.

      • »
        »
        »
        »
        3 months ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        I remember the std :: sort use three algorithms, First it takes the quicksort while the len of the array Higher than a threshold, Because the quicksort uses recursion, when the len lower than a threshold it takes insertation sort. Because the part of the array is almost in order, so it takes about O(N) time. When the recursive level is too deep. (sorry for my poor English) It takes another Nlogn algorithm — heap sort, in order to avoid the N^2 quick sort

        so the std :: sort is an Introspective Sort Algorithm by using three sort algorithms。

»
6 years ago, # |
  Vote: I like it +2 Vote: I do not like it

By the way as far as I know in Java 7 TimSort is used instead of MergeSort. But it's O(nlogn) and stable too

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Here is a blog which might be helpful :
Problems with Java for Competitive Programming