Implement comparator in java

Question

I am a java newbie and I am trying to understand the code given here.

What I fail to understand is that in that class StringLengthComparator, they form the "skeleton" to compare 2 objects: String o1, String o2.

When they apply the class however, there are 6 strings which are passed to StringLengthComparator and it yields the correct result.

My question is how come when only 2 objects are compared in the class, but when 6 strings are passed it yields the right result?

Obviously, I am missing something fundamental here, and therefore, any guidance on this would be great.

Answer 1

Comparator (is used in Collections in java) which is used to specify sorting parameter like length or alphabetic order or etc.. by default it compares alphabetically for the strings so if you want to compare two strings by length of it then it will compare it by length by overriding Comparator.

 Arrays.sort(strs, new StringLengthComparator());

will sort the array of strings for each element in array strs with specifying the comparator StringLengthComparator that says that comparision parameter will be the length of string.

Answer 2

My question is how come when only 2 objects are compared in the class, but when 6 strings are passed it yields the right result?

The object's .compare method compares two strings at a time. The Arrays.sort method calls .compare on the supplied object several times, passing it different pairs of strings from the full set of 6, using the resulting information to sort the array.

Answer 3

Java's internal sorting algorithm(or any sorting algorithm for that matter) needs to know how to sort objects other than the primitives.

For example, java knows how to sort an array of integers because it has an established natural ordering. [For any sequence of integers (a,b) a would come before b, if a is less than b] This isn't true for all objects that can be created by the user. So for these objects we should let know java on how to sort and the Comparator.compare() is used for this purpose.

As any sorting algorithm needs to know how to compare just two objects of the same type, two parameters is plenty for Comparator.compare()

Answer 4

When you create something like a StringLengthComparator, you the developer implement the :

int compare(T o1, T o2)

method as part of the contract for implementing the Comparator interface. When encountering any two T objects, this method returns 1, 0, or -1 depending on if o1 is larger than, equal to, or less than o2, respectively.

When implemented correctly, this is the only requirement for any sorting algorithm to be generically plugged into your code, whether its mergesort, quicksort, or whatever other sorting routine you can think of.

The Arrays class uses this property when you invoke :

static void sort(Object[] a, Comparator c) 

If you have any further doubts, download the JDK source and see how it's done. As an exercise you should write something like a BubbleSort algorithm that takes a comparator and sorts the array using it.

Answer 5

I see your confusion. It's not really a "skeleton", it's simply the algorithm for determining the relationship between one thing and another. So the sort then calls the comparator when it needs to determine this relationship. You can for example get a descending sort by making the relationship backwards in your comparator.

Answer 6

Basically, the array of strings (6 strings) is not passed to StringLengthComparator but to Arrays.sort which uses the StringLengthComparator to compare the strings one by one and sort the array

Answer 7

Ultimately, this is how Arrays.sort is implemented. You can look at the Java 6 API, but you won't be satisfied with that until you look at the source code for yourself - check the file /jdk/src/share/classes/java/util/Arrays.java in the source code directory.

What this method is doing is taking in an array, then the Comparator, then running a version of merge sort on the entire array using that Comparator. You would be well served if you looked into mergesort to fully grasp the nature of this method.

Here's the snippet of the code, since Java 6/7 is open source. Again, look into mergesort and you'll be able to see why this works the way it does.

---

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);
}