CODEWITHSUNDEEP
javaperformancesortingarraylist
MARCELO
MARCELO

Reputation: 43

How can I sort an ArrayList faster?

I'm doing a class project and I need to sort ArrayLists of custom objects based on the values of their int attributes.

I'm currenly using something like this:

public static void Sort(ArrayList <MyObject> objectList){

    for (int i = 0; i < list.size()-1; i++){

        for (int j = 0; j < list.size()-1; j++){

            if (objectList.get(j).getA() > objectList.get(j+1).getA()){

                Collections.swap(objectList, j, j+1);
            }
        }    
    }    
}

The program works well if the ArrayList has less than 10^4 elements. But if I try to sort 10^5 elements it takes several minutes, and I need to sort 10^6 elements. Any suggestions?

Upvotes: 2

Views: 3326

Answers (2)

Amir Raminfar
Amir Raminfar

Reputation: 34150

Currently, your implementation is O(n^2) which means that as the array grows, the time will expand quadratically.

Without going into a lot of details of using mergesort which is O(log(n) x n), the fastest way is to use Java's built-in solution for sorting. 

Collections.sort(list);

Link to API. There is also Collection.sort(list, comparator) which allows you to provide your own comparator.

Do you want it to be even faster? You can use the Java's new feature which allows you to sort with multiple cores in parallel. Here is the API. Notice that Arrays.sort() and Arrays.parallelSort() take an array as the first parameter. You will need to convert a list to an array using list.toArray().

Finally, do note that List#sort() was introduced only in Java 8.

Upvotes: 2

Ousmane D.
Ousmane D.

Reputation: 56413

Use the List::sort method:

objectList.sort(Comparator.comparing(MyObject::getA));

As @lexicore has mentioned below, it seems like getA() returns a numeric type, in which case if it returns int then it's better to use comparingInt instead of comparing above, if it's long use comparingLong or if it's a float/double then use comparingDouble for better performance.

Upvotes: 5

Related Questions