Sorting an array of comparable interface

Question

I have written sorting methods for an array of comparables, insertion, merge, and selection, I've done this by altering code I had before from sorting an int array, and I just changed things from int to Comparable. However, When I was doing it for int arrays, I knew very well how to actually use the method, for example this is my my selection sort for ints:

 public void selectionSort(int[] list){
    for (int i=0;i<list.length;i++){
        for (int si=i;si<list.length;si++){
            if (list[si]<list[i]){
                int temp=list[i];
                list[i]=list[si];
                list[si]=temp;
            }
        }
    }        
}

and this is the code which ends up using this method:

public static void main(String[] args) {
    Scanner in=new Scanner(System.in);
    int numItems,searchNum,location;
    Sorts sort=new Sorts();        
    int[]test;        
    System.out.print("Enter the number of elements: ");
    numItems=in.nextInt();
    test=new int[numItems];

    for (int i=0;i<test.length;i++){
        test[i]=(int)(100*Math.random());
    }

    System.out.println("Unsorted: ");
    displayArray(test);
    sort.selectionSort(test);
    System.out.println("Sorted: ");        
    displayArray(test);    

and everything works fine, but for my comparable selection sort, I have this code:

public static void selectionSort(Comparable[] list){   
for (int i=0;i<list.length;i++){
        for (int si=i;si<list.length;si++){
            if (list[si].compareTo(list[i])<0){
                Comparable temp=list[i];
                list[i]=list[si];
                list[si]=temp;
            }
        }
       }
    }

but when I get to writing the code to test out this method, I just have no idea how to approach it, I don't know how I can make an array of Comparable interfaces, the concept is just so confusing for me and I can't find a way to make it work.

Answer 1

Integer, for instance, implements Comparable, so it's legal to write:

Comparable[] list = new Comparable[3];
list[0] = Integer.valueOf(3);
list[1] = Integer.valueOf(2);
list[2] = Integer.valueOf(3);

You can see all the implementors of Comparable in the standard JDK by looking at the JavaDoc.

The trouble is (and you should see some compiler warnings about this), you can't both specify the generic parameter for Comparable and make an array of the parameterized object, that is, it's not legal to write:

 Comparable<Integer>[] list = new Comparable<Integer>[3];

Even if it were legal to write that, you'd run into a new issue, since you need the concrete type to use in the Comparable<T> test. Comparable<T> requires a comparison to an object of type T (the method is int compareTo(T o)). In essence, your code only works because it's unparameterized (T is implicitly Object, everything extends Object), but you're losing some compile-time safety checks along the way.

It might make more sense to parameterize your input by an array of generic parameterized Comparable objects rather than as an array of Comparable. Writing this using generics is a little bit tricky, the method prototype would look something like:

 public static void <T extends Comparable<T>> selectionSort(T[] list) {
     // legal to call list[k].compareTo, because `T` is guaranteed to be `Comparable`
 }

Notably, this will work for any non-primitive object type T that implements Comparable<T>, such as an Integer[] or Double[], but not an int[].