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-12T23:13:39.390

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 '18 at 23:13

answered May 12 '18 at 23:00

Ousmane D.

54,915
8
91
126

Most probably `comparingInt`, `comparingLong` or `comparingDouble` since `getA` seems to be some numeric type. – lexicore May 12 '18 at 23:02
@lexicore agreed on using those aforementioned methods but I don't know the exact primitive type hence using `comparing`. – Ousmane D. May 12 '18 at 23:04

Amir Raminfar · Answer 2 · 2018-05-12T23:25:51.907

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 '18 at 23:25

answered May 12 '18 at 23:20

Amir Raminfar

33,777
7
93
123

1

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. – Ousmane D. May 12 '18 at 23:22
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. – Amir Raminfar May 12 '18 at 23:24
@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. – lexicore May 12 '18 at 23:26
Also as JDK-8, `list.sort` internally calls `Arrays.sort()` :) – Amir Raminfar May 12 '18 at 23:28
1

@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. – Ousmane D. May 12 '18 at 23:33
1

@Aominè You're right of course. Unfortunately writing a correct micro-benchmark is quite hard. There are some experiments available which might be useful: https://stackoverflow.com/a/17328147/303810 – lexicore May 12 '18 at 23:39
In the context of >>this<< question, the OP merely wants to sort 10^6 elements in a reasonable time. Any standard O(nlogn) implementation should be good enough to achieve that. ("As fast as possible" is not necessary ... here.) – Stephen C May 12 '18 at 23:56

How can I sort an ArrayList faster?

2 Answers2