How can I sort an ArrayList faster?

Question

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?

Ousmane D. · Accepted Answer · 2018-05-12 23:13:39Z

5

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.

edited May 12, 2018 at 23:13

answered May 12, 2018 at 23:00

Ousmane D.

56.6k8 gold badges101 silver badges134 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

lexicore Over a year ago

Most probably comparingInt, comparingLong or comparingDouble since getA seems to be some numeric type.

Ousmane D. Over a year ago

@lexicore agreed on using those aforementioned methods but I don't know the exact primitive type hence using comparing.

Amir Raminfar · Accepted Answer · 2018-05-12 23:25:51Z

2

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.

edited May 12, 2018 at 23:25

answered May 12, 2018 at 23:20

Amir Raminfar

34.2k8 gold badges97 silver badges125 bronze badges

7 Comments

Ousmane D. Over a year ago

As of JDK-8 Collections.sort(list); and Collection.sort(list, comparator) internally call list.sort as shown in my answer so it's no different solution really. plus before suggesting to use parallel streams or parallel sort I'd say measure, measure and measure to see if you'll gain any benefit.

Amir Raminfar Over a year ago

There is a difference depending on which Java you use. list.sort() was introduced in Java 1.8. It will not work on older versions.

lexicore Over a year ago

@Aominè Collections.sort and List.sort are same eggs, side view, indeed. But there's no List.parallelSort which is the added value of this answer.

Ousmane D. Over a year ago

@lexicore Right, I like the suggestion although I'd add that one should measure carefully when attempting to use parallelSort or the parallel stream API to make sure you're gaining any benefit or losing on performance time.

lexicore Over a year ago

@Aominè You're right of course. Unfortunately writing a correct micro-benchmark is quite hard. There are some experiments available which might be useful: stackoverflow.com/a/17328147/303810

|

Collectives™ on Stack Overflow

How can I sort an ArrayList faster?

2 Answers 2

2 Comments

7 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

7 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related