Method shown below can do “Insertion Sorting” for integer arrays. Modify it so that it can sort any type array, object types and primitive types.

Question

public static void sort(int[] data) {

int i, j, temp;

for(i=1; i<data.length; i++) {

temp = data[i];

for(j=i-1; j>=0; j--) {

if(data[j]>temp) data[j+1] = data[j];

else break;

}

data[j+1] = temp;

}

}

Answer 1

Let's take it one step at a time, and re-implement it for an array of doubles.

All the operations in your method are the basic mathematical operations, so the same operations that you're using for integers should also work for doubles. So, in essence, not much more should be required other than to change the argument type of the code you've written, to make it support doubles:

public static void sort(double[] data) {

int i, j, temp;

for(i = 1; i < data.length; i++) {

temp = data[i]; //Compiler error: assigning a double value to an int

for(j = i - 1; j >= 0; j--) {

if(data[j] > temp)

data[j + 1] = data[j];

else

break;

}

data[j + 1] = temp;

}

}

But if you try this, you'll get a compiler error on the line with the comment, since you're trying to assign a double value to an integer variable. Now, in your previous version, i, j, and temp are all integers, and so were declared on the same line, but the variables have different purposes. i and j are simply used for iteration in the for loops, but temp needs to hold an actual value from the array. As such, temp cannot simply be an integer, but instead needs to be of the type of variable being sorted, in this case double. Let's make this fix:

public static void sort(double[] data) {

int i, j;

double temp; //New line here: temp holds values from the array, and so needs to be of the same type as the array

for(i = 1; i < data.length; i++) {

temp = data[i];

for(j = i - 1; j >= 0; j--) {

if(data[j] > temp)

data[j + 1] = data[j];

else

break;

}

data[j + 1] = temp;

}

}

Let's try some test code:

public static void main(String[] args) {

double[] test = {6.0, 3.0, 8.5, 2.3, 9.2, 4.7, 1.3, 10.1};

sort(test);

System.out.println(java.util.Arrays.toString(test));

}

And it seems to work! We get an output of [1.3, 2.3, 3.0, 4.7, 6.0, 8.5, 9.2, 10.1], which is correct.

Now, let's try some more test code:

public static void main(String[] args) {

int[] test = {6, 3, 8, 2, 9, 4, 1, 10};

sort(test); //Compiler error: can't pass an int[] to a method expecting a double[]

System.out.println(java.util.Arrays.toString(test));

}

Unfortunately, we run into another issue. Primitive array types are not type-compatible with each other; in other words, if a method expects a double[], you cannot pass in an int[] or any other primitive array type. So, in order for this method to support all primitives, you'll have to implement separate versions for all of the primitive data types.

Fortunately, the code we've written can be easily adapted to support more primitive data types, as we showed above: all we need to do is change the argument type, and change the type of temp to the type we're sorting. So, in order to make it support all of the primitive data types, we just need to implement overloaded versions of the method for each data type.

Now that we've implemented it for all the seven primitive sortable types, we can finally come to the object types.

Before we come to this, we have to consider that not every object in Java can be sorted. For example, strings can be sorted, but other things like input streams cannot be sorted. Java provides an interface called Comparable, that a class can implement to indicate that objects of its type can be compared (and thus sorted).

So, all we need to do is overload the method once again, substituting the primitive data type for the Comparable type. (Remember, if a class implements Comparable, its objects are also of type Comparable.):

public static void sort(Comparable[] data) {

int i, j;

Comparable temp;

for(i = 1; i < data.length; i++) {

temp = data[i];

for(j = i - 1; j >= 0; j--) {

if(data[j] > temp) //Compiler error: can't use > operator on object types

data[j + 1] = data[j];

else

break;

}

data[j + 1] = temp;

}

}

First of all, we have one major thing going in our favor: unlike primitive array types, object array types are type-compatible, meaning that you can pass in a String[] to this method and it would work. So we can implement just one overloaded method for object types, rather than having to overload this method for different types like we had to do for the primitive types.

The code above doesn't compile, though: we get a compiler error on the commented line because we can't use logical operators on object types. This line is the one where we're doing the actual comparison: we need to replace the logical operator with the call to the method in the Comparable interface that actually compares objects: compareTo(). The method compareTo() returns a negative number, a positive number, or zero, based on whether the object passed in is less than, greater than, or equal to the object it's being invoked on. Think of it like this way: a < b is the same thing as a - b < 0, which is analogous to a.compareTo(b) < 0. Let's rewrite that line to use that method:

public static void sort(Comparable[] data) {

int i, j;

Comparable temp;

for(i = 1; i < data.length; i++) {

temp = data[i];

for(j = i - 1; j >= 0; j--) {

if(data[j].compareTo(temp) > 0) //Rewritten line with compareTo

data[j + 1] = data[j];

else

break;

}

data[j + 1] = temp;

}

}

And there you have it: the sort() method is implemented for all primitive types (except boolean), and for all object types that can be sorted, via seven separate overloaded versions for each primitive type and one additional for the object types.