help for writing a fast sort

I am writing a java application. I have a class named Node. I have created an ArrayList object and add some nodes in it. , each node has an integer data and a double probability. I want to sort the node in the arrayList increasingly by their probability. I have written the following method:

     private void sort(ArrayList<Node> list2) {
    int n = list2.size();
    for (int i = 1; i < n; i++) {
        int m = list2.get(i);
        int j = i - 1;
        while ((j >= 0) && (list2.get(j).prob > m.prob开发者_开发技巧))
            list2.set(j + 1, list2.get(j--));
        list2.set(j + 1, m);
      }

     }

But it isn’t a fast method for sorting. How can I sort faster? Can I use the method Collections.sort() in java for this aim? How ? would you please guide me?

Yes, you can use Collections.sort() - and that's almost certainly the right thing to do. You should at least do that to start with, and benchmark it to see if it's fast enough. You may be able to do better if you have more information about the list (e.g. it's likely to be "mostly sorted" to start with) but taking a simple approach is a good starting point.

Note that your sample code doesn't correspond to your description - you've described an ArrayList<Node> but your code is just for an ArrayList<Integer>.

Yes, you can (and should) use Collections.sort(). This way of sorting is already optimized, and probably will always run faster than an implementation you are likely to write yourself.

However, your code does not currently apply to Collections.sort(). To do so, the objects you place in your list should have both a 'data' and 'probability' field.

Here's a quick example:

public class DataProbability implements Comparable<DataProbability> {
    private int data;
    private double probability;

    public int getData() {
        return data;
    }

    public double getProbability() {
        return probability;
    }

    public int compareTo(DataProbability pProb) {
        return Double.compare(getProbability(), pProb.getProbability());
    }
}

// Later, with your list
List<DataProbability> lDataList = new ArrayList<DataProbability>();
// Add some elements
Collections.sort(lDataList);

When sorting a list, you have 2 options:

• Making sure the 'objects' to be sorted implement the Comparable interface (this is what I just used
• Or you can also specify a Comparator to use when calling Collections.sort()

Comparable interface needs to be implemented when sorting user defined objects. You will also need to override equals() and hashcode() methods for that. However, this is not required for sorting a list which contains only primitive data type objects.