Fastest way to sort an array of objects in java

Question

I have a Class called apple which contains 3 values as int x, int y and int weight. Then i created an array of apple type objects. Now i want to sort the the array of objects based on weight meaning the the apple object with the lowest weight should be first and so on.

I know there are quite a few ways to achieve this by using Arrays.sort etc or comparators.

I was wondering what is the fastest way of doing this sort in Java? There can be a case where i have 500,000 objects so i want to know which sort i should use, more importantly which approach will give me best approach. i have even wrote my own quick sort with Hoare partition.

Code for Apple class

public class Apple {
    public int x;
    public int y;
    public int weight;

    public Apple(int a, int b, int w) {
        x = a;
        y = b;
        weight = w;
    }
}

Code for main class

public class main {
    static Apple[] appleArray;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int size = sc.nextInt();
        int totalApples = sc.nextInt();
        appleArray = new Edge[totalApples];
        int x = 10;
        int y = 20;
        int w = 30;

        for (int i = 0; i < size; i++) {
            appleArray[i] = new Apple(x, y, w);
            x++;
            y++;
            w++;
        }
        //Now i want to sort array of apple objects based on weight
    }
}

Answer 1

This book has a useful cheat sheet for deciding the optimal sort for your needs: https://www.safaribooksonline.com/library/view/algorithms-in-a/9780596516246/ch04s09.html

The easiest solution

The Arrays.sort command uses a quicksort implementation, which is suitable for many situations. For your example code this might be:

Arrays.sort(appleArray, new Comparator<Apple>(){  
    @Override  
    public int compare(Apple apple1, Apple apple2){  
         return apple1.weight - apple2.weight;  
    }  
}); 

The fastest solution

In your case you have a large array containing repetitions, for example 50,000 apples in your array might all weigh 3 ounces... You might therefore opt to implement a bucket sort to improve performance over a quicksort, which can be wasteful under such conditions. Here is an example implementation.

Perhaps benchmark a few researched choices, using the Java API when it suits, to determine the best solution for your input set.

Answer 2

I would first use Java API. If this is not fast enough then I would search for a optimized sorting library.

Also consider a database, DB engines are fast and optimized for sorting large data sets.