CODEWITHSUNDEEP
javasortingcomparatorcomparable
benz
benz

Reputation: 4629

Comparator compare() method sorting confusion

I am doing self-test question from Kathy and Seirra book. One of the question went wrong, so i was trying in IDE. My confusion can be found from this image. Main question is when i debugged it, i had put a debugging point in compare method. If the tooltip can be noticed o1 holds value pen. I thought o1 should be map and o2 should be pen. Can someone explain me this confusion?

Comparator Confusion

Upvotes: 1

Views: 779

Answers (4)

uraimo
uraimo

Reputation: 19821

The order doesn't matter when you implement a Comparator, you just need to conform to that Class contract and implement it as required. You can only deduce the order of the calls knowing the input and the implementation.

Just for the sake of completeness, from OpenJDK 7, this is the implementation of Arrays.sort that uses merge sort (analysis below):

public static <T> void sort(T[] a, Comparator<? super T> c) {
    T[] aux = (T[])a.clone();
    if (c==null)
       mergeSort(aux, a, 0, a.length, 0);
    else
       mergeSort(aux, a, 0, a.length, 0, c);
}

And Arrays::mergeSort:

private static final int INSERTIONSORT_THRESHOLD = 7;

private static void mergeSort(Object[] src,
                              Object[] dest,
                              int low, int high, int off,
                              Comparator c) {
    int length = high - low;

    // Insertion sort on smallest arrays
    if (length < INSERTIONSORT_THRESHOLD) {
        for (int i=low; i<high; i++)
            for (int j=i; j>low && c.compare(dest[j-1], dest[j])>0; j--)
                swap(dest, j, j-1);
        return;
    }

    // Recursively sort halves of dest into src
    int destLow  = low;
    int destHigh = high;
    low  += off;
    high += off;
    int mid = (low + high) >>> 1;
    mergeSort(dest, src, low, mid, -off, c);
    mergeSort(dest, src, mid, high, -off, c);

    // If list is already sorted, just copy from src to dest.  This is an
    // optimization that results in faster sorts for nearly ordered lists.
    if (c.compare(src[mid-1], src[mid]) <= 0) {
       System.arraycopy(src, low, dest, destLow, length);
       return;
    }

    // Merge sorted halves (now in src) into dest
    for(int i = destLow, p = low, q = mid; i < destHigh; i++) {
        if (q >= high || p < mid && c.compare(src[p], src[q]) <= 0)
            dest[i] = src[p++];
        else
            dest[i] = src[q++];
    }
}

In your example, this is true: length < INSERTIONSORT_THRESHOLD so an insertion sort will be actually performed for this small 4 elements array.

Edit: Wrong mergeSort, fixed.

Upvotes: 1

Jeremy Lautman
Jeremy Lautman

Reputation: 16

How did the question go wrong? What was the original question?

Arrays.sort(Object[]) uses Mergesort, but that shouldn't really matter if all you are worried about is getting a sorted array. As long as you match the requirements of the Comparator interface (http://docs.oracle.com/javase/7/docs/api/java/util/Comparator.html) your array will come out sorted correctly.

Upvotes: 0

Stefaan Neyts
Stefaan Neyts

Reputation: 2092

You can check the source of Arrays.sort method on grepcode and understand it better now:

http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/util/Arrays.java#Arrays.sort%28java.lang.Object%5B%5D%2Cjava.util.Comparator%29

Upvotes: 1

Chin
Chin

Reputation: 20675

I don't know why you expect o1 should be map and o2 should be pen. There is no guarantee for that, and in fact, you shouldn't care about it when you implement the compare() method.

Upvotes: 0

Related Questions