I was assigned an exercise at school: I have to define a class ListSorter (or ArraySorter) that implements many sorting algorithms we studied and uses them to sort an integer array.
I decided to try to make, instead, a generic *Sorter<> that could sort data of any type.
Problem is, how do you even manage arrays and generics? I've found many difficulties (couldn't even use List.toArray() because, if I remember well, it needs an array of the desired type to be passed, else the returned array would be Object[] --> ClassCastException).
That's why I switched to sorting arrays, hoping that it would make my work easier... it didn't.
import java.util.List;
/**
* The class ListSorter contains many implementations of famous sorting algorithms, whether their
* performances are optimal or not.
*
*/
public final class ListSorter<T extends Comparable<T>> {
/**
* Sorts a list using the Insertion Sort algorithm, in time O(n^2). Actually, if the list is already
* partially sorted, this method reaches better performances.
* @param list the list to be sorted
* @param <T> the type of the elements of the list
*/
public void insertionSort(List<T> list) {
for (var i = 1; i < list.size(); i ) {
var current = list.get(i);
int j = 0;
// Trova il posto giusto per current
while (j <= i - 1 && list.get(j).compareTo(current) <= 0)
j ;
// Scambia l'elemento corrente con l'ultimo
list.set(i, list.get(list.size() - 1));
// Fai posto per inserire current al posto giusto, shiftando gli elementi a destra
for (var k = list.size() - 1; k > j; k--) {
list.set(k, list.get(k - 1));
}
list.set(j, current);
}
}
/**
* Sorts a list using the Bubble Sort algorithm, in time O(n^2). Actually, it is far more probable
* that this method is going to reach better performances.
* @param list the list to be sorted
* @param <T> the type of the elements of the list
*/
public void bubbleSort(List<T> list) {
boolean listChanged;
do {
listChanged = false;
for (var i = 0; i < list.size() - 1; i ) {
if (list.get(i).compareTo(list.get(i 1)) > 0) {
var temp = list.get(i);
list.set(i, list.get(i 1));
list.set(i 1, temp);
listChanged = true;
}
}
} while (listChanged);
}
public void heapSort(List<T> list) {
// TODO
}
public void mergeSort(T[] array) {
mergeSort(array, 0, array.length - 1);
}
private void mergeSort(T[] array, int start, int end) {
if (start >= end)
return;
int mid = (start end) / 2;
mergeSort(array, start, mid);
mergeSort(array, mid 1, end);
merge(array, start, mid, end);
}
private void merge(
T[] array, int firstPointer, int firstTerminator, int secondTerminator) {
var auxArray = getGenericArrayInstance();
int secondPointer = firstTerminator 1;
int auxPointer = 0;
while (firstPointer <= firstTerminator && secondPointer <= secondTerminator) {
if (array[firstPointer].compareTo(array[secondPointer]) <= 0) {
auxArray[auxPointer] = array[firstPointer];
firstPointer ;
} else {
auxArray[auxPointer] = array[secondPointer];
secondPointer ;
}
auxPointer ;
}
}
// I know this may be bad practice, but I saw it here and needed to try.
// Didn't solve my problem, though, as I can't decide the length of
// the array --> IndexOutOfBoundsException
@SafeVarargs
private T[] getGenericArrayInstance(T ...dummyValues) {
return dummyValues;
}
My question, now, is: am I trying to use generics in the wrong place, am I using the generics wrong, or what? I've never worked with them so deeply, so I would like to see what you can do in these situations.
CodePudding user response：
In Java, arrays and generics unfortunately don't work well together. The main reason for that is because arrays need runtime type information (an array knows at runtime what the type of its elements is), but generics work with type erasure (type parameters only exist at compile time). One of the consequences is that you cannot create an instance of an array of a generic type T with new T[] - the problem is that what T is, is unknown at runtime.
The getGenericArrayInstance method that you have in your question above is not a workaround for this:
private T[] getGenericArrayInstance(T ...dummyValues) {
return dummyValues;
}
This method does nothing. It just returns the array that you pass to it. Calling it with zero arguments is just like calling it with a zero-length array, so in that case it will return a zero-length array.
There is a way to create an instance of T[] using reflection. But it requires you to explicitly pass the type of the elements of the array. You could write it like this:
import java.lang.reflect.Array;
// ...
private T[] getGenericArrayInstance(Class<T> elementType, int length) {
return (T[]) Array.newInstance(elementType, length);
}
Note that this means you will have to pass elementType through the whole chain of methods as well. So you'll get:
public void mergeSort(T[] array, Class<T> elementType) {
mergeSort(array, elementType, 0, array.length - 1);
}
private void mergeSort(T[] array, Class<T> elementType, int start, int end) {
if (start >= end) return;
int mid = (start end) / 2;
mergeSort(array, elementType, start, mid);
mergeSort(array, elementType, mid 1, end);
merge(array, elementType, start, mid, end);
}
private void merge(T[] array, Class<T> elementType, int firstPointer, int firstTerminator, int secondTerminator) {
var auxArray = getGenericArrayInstance(elementType, array.length);
// ...
}
And you'll have to call it like this:
String[] names = {"c", "a", "b", "z", "d"};
ListSorter<String> sorter = new ListSorter<>();
// Note that you have to pass String.class here
sorter.mergeSort(names, String.class);
Note: This solves the problem of creating a T[]. If you fix this the code still won't work, because in the merge method you're putting the result of the sort in auxArray, but you're not updating the original array.
(p.s.: I have a course on Pluralsight about arrays; towards the end of the course I explain exactly what the problems are with arrays and generics).