Collections.sort() leaves my list unsorted

Question

I'm trying to sort an ArrayList of PostingsEntry objects according to the score attribute of the PostingsEntry objects. The list resides in a PostingsList object that has the sort() method.

public class PostingsEntry implements Comparable<PostingsEntry>{

    public int docID;
    public double score = 0;
    private TreeSet<Integer> positions = new TreeSet<Integer>();
    /** 
     *  PostingsEntries are compared by their score (only relevant
     *  in ranked retrieval).
     *
     *  The comparison is defined so that entries will be put in 
     *  descending order.
     */

    public int compareTo( PostingsEntry other ) { 
        return Double.compare( other.score, score );
    } 
}

public class PostingsList{

    private int position = 0;
    /** The postings list */
    private ArrayList<PostingsEntry> list = new ArrayList<PostingsEntry>();

    private class PostingsEntryComparator implements Comparator<PostingsEntry>{
        @Override
        public int compare(PostingsEntry pA, PostingsEntry pB){
            return pA.docID - pB.docID;
        }   
    }   
    /** Number of postings in this list. */
    public int size() {
        return list.size();
    }   

    /** Returns the ith posting. */
    public PostingsEntry get( int i ) { 
    return list.get( i );
    }      

    public void sort(){
        Collections.sort(list, new PostingsEntryComparator());
    }   

}

I'm trying to sort the list here:

// sort postingsList
postingsList.sort();

And I print the results:

for(int i=0; i<postingsList.size(); i++){
    System.out.println(index.docNames.get(postingsList.get(i).docID));
    System.out.printf("score: %f\n\n", postingsList.get(i).score);
}

But I get:

davisWiki/Zombie_Attack_Response_Guide.f
score: 0,019064

davisWiki/EvanGray.f
score: 0,004368

davisWiki/Mortal_Forever.f
score: 0,002708

davisWiki/JasonRifkind.f
score: 0,767518

davisWiki/Measure_Z.f
score: 0,031980

Which shows that the list has clearly not been sorted. Where am I going wrong?

Answer 1

Your call of sort passes a different comparator:

public void sort(){
    Collections.sort(list, new PostingsEntryComparator());
}

For the purpose of this sort, this PostingsEntryComparator replaces the "natural order" by score, as established by PostingsEntry's implementation of Comparable<PostingsEntry>. Hence, the entries are compared on their docID. If you print docID in place of score, you will see that your list is properly ordered according to IDs.

Note: Subtracting IDs of two items being compared could produce incorrect results due to integer overflow. Use Integer.compare instead, in the same way that you correctly used Double.compare in PostingsEntry.compareTo.

Answer 2

When you call

 Collections.sort(list, new PostingsEntryComparator());

you are sorting by PostingsEntryComparator, which compares the docIDs.

If you want to sort by score, you need to use the Comparable implementation of your PostingsEntry, which you can do by calling Collections.sort() without passing a Comparator:

Collections.sort(list);