SCJP Objective 6.5 Question

[karl czukoski]

I found this question to be a bit challenging and was wondering if someone could walk through the question in detail to help me better understand.

import java.util.*
public class VLA2 implements Comparator<VLA2> {
  int dishSize;
  public static void main(String[] args) {
    VLA2[] va = {new VLA2(40), new VLA2(200), new VLA2(60) };

    Arrays.sort(va. va[0]);
    int index = Arrays.binarySearch(va, new VLA2(40), va[0]);
    System.out. print(index + " ");
    index = Arrays.binarySearch(va, new VLA(80), va[0]);
    System.out.print(index);
   }
   public int compare(VLA2 a, VLA2 b) {
      return b.dishSize - a.dishSize;
   }
  VLA2(int d) { dishSize = d }
}

result is 2 -2

[dennis deems]

import java.util.Arrays;
import java.util.Comparator;

public class VLA2 implements Comparator<VLA2> {

    // This class implements Comparator for itself. This
    // means that anywhere we must pass a parameter of
    // Comparator<VLA2>, we can pass an instance of the class.

    int dishSize;

    public static void main(String[] args) {

	// create three VLA2 objects with unique dish sizes.
	// store them in an array named va.
	VLA2[] va = { new VLA2(40), new VLA2(200), new VLA2(60) };

	// sort the array using the instance located at array index zero for the comparator
	// note we could use any of the other instances and get the same result
	Arrays.sort(va, va[0]);

	// note the compare method sorts elements in reverse order
	// so now the array looks like:
	// {vla2(200), vla2(60), vla2(40)}

	// now we are performing a binary search in the array va
	// we ask for a VLA2 object whose dish size is 40
        // the new VLA2 object is a dummy we pass to the search
        // that holds the attributes we wish to find
	// finally, we pass the comparator we wish the binary search to use
	int index = Arrays.binarySearch(va, new VLA2(40), va[0]);

	// after the sort, the desired element is at index 2
	System.out.print(index + " ");

	// Now we search again for an element that is not in the array.
	// This time, the returned value will indicate the insertion point
    // -- the index where the element WOULD be if it HAD been found
	// according to this formula: (-(insertion point) - 1)

	// If we get a positive value from binarySearch, then we know
	// the element was found in the array. Negative value tells us
	// it was NOT found.

	index = Arrays.binarySearch(va, new VLA2(80), va[0]);

    // there is no VLA2 object in the array with dish size of 80
	// the element we wanted to find would be inserted at index 1
	// so the value of "index" is -2
	System.out.print(index);
    }

    public int compare(VLA2 a, VLA2 b) {

        // Sorting in reverse order!
        return b.dishSize - a.dishSize;
    }

    VLA2(int d) {

        dishSize = d;
    }
}

[Shaikh Ali]

Let me know if the comments help.

import java.util.*  
public class VLA2 implements Comparator<VLA2> {  // Comparator declaration (used by Array.sort() in the code)
  int dishSize;  
  public static void main(String[] args) {  
    VLA2[] va = {new VLA2(40), new VLA2(200), new VLA2(60) };  // array of 3 VLA2 objects
  
    Arrays.sort(va. va[0]);  // va array sorted in descending order (200, 60, 40)
    int index = Arrays.binarySearch(va, new VLA2(40), va[0]);  // va searched for 40 with comparator, the answer is 2 using 0-based index
    System.out. print(index + " ");  
    index = Arrays.binarySearch(va, new VLA(80), va[0]);  // va searched for 80 with comparator, if there is no matching object, the answer is the negative of insertion position subtract 1, 
                                                                                    // so the 80 should be at position 1 of the array if it existed, so the answer is -1-1=-2
    System.out.print(index);  
   }  
   public int compare(VLA2 a, VLA2 b) {  // Comparator implemented
    return b.dishSize - a.dishSize;  // sorts in descending order
   }  
  VLA2(int d) { dishSize = d }  

[karl czukoski]

I am still having a difficult time understanding the descending order sort sequencing using the overridden compare, could i ask you to explain this in a little more detail?

[dennis deems]

Remember the contract of the Comparator interface:

compare returns a zero if the first argument is equal to the second.
compare returns a negative integer if the first argument is less than the second
compare returns a positive integer if the first argument is greater than the second.

This language could be more explicit, but "a less than b" means that
a comes before b in the sort order. And "a greater than b" means that
a comes after b in the sort order.

Comparing numerical arguments is simple; we can do arithmetic on the arguments.
For an ascending sort we can return (first argument) - (second argument).

We could implement a comparator for Integers like this:

class CompareInt implements Comparator<Integer>{
    public int compare(Integer a, Integer b) {
        return a-b;
    }
}

Suppose we are sorting Integers in ascending order, and we call compare(3, 7).
Our comparator subtracts 7 from 3 and returns the result -4.
This negative value tells the sort routine calling compare that argument a comes before argument b.
The sort routine doesn't care about the actual value -- just whether it is negative, zero, or positive.
If we call compare(6, 5), the comparator returns the value 1, telling us that 6 comes after 5.

If we want to reverse the sort order, to perform a descending sort, all we need do is swap the arguments:

class ReverseCompareInt implements Comparator<Integer>{
    public int compare(Integer a, Integer b) {
        return b-a;
    }
}

Now the same call compare(3, 7) will subtract 3 from 7 and return 4,
and signify that 3 comes after 7 in the sort order.
Likewise compare(6, 5) now returns -1, meaning that 6 comes before 5.
All the values returned from the new implementation
are the inverse of those returned by the original implementation.

Note that in either implementation, a call like compare(5, 5) will return zero.