Is there a way to use Java generic types to write sorting algorithms?

Question

I've been relearning Java after a long time, and I'm trying out writing some sorting algorithms. The (rather outdated) textbook I have uses the Comparable interface to sort objects. Since Comparables are now generic types, doing this gives me a lot of warnings about raw types when compiling. After some research, it looks like I can do something like, for example:

public class Sorting
{
    public static <T extends Comparable<T>> void quickSort(T[] list, int start, int end)
    {
        /*...*/
        while((list[left].compareTo(list[pivot]) < 0) && (left != right)) // for example
            left++;
        /*...*/
    }
}

The problem with this is that the naive way of calling this method does not work:

public class SortingTest
{
    public static void main(String[] args)
    {
        // Produces an error, cannot create arrays of generic types
        Comparable<Integer>[] list = new Comparable<Integer>[100];

        /* fill the array somehow */

        Sorting.quickSort(list, 0, 99);
    }
}

It is illegal to create an array of generic types in Java. The problem only gets worse if I try to implement a merge sort, since that requires creating arrays of Comparable types inside the merge sort method itself.

Is there any way to handle this situation elegantly?

You can use the Comparator interface docs.oracle.com/javase/7/docs/api/java/util/Comparator.html — ares
– ares, Commented Sep 21, 2014 at 19:50
This is not the question … he want to write its own generic sorter ! You can reopen. — Nicolas Albert
– Nicolas Albert, Commented Sep 21, 2014 at 19:53
Note that this question does not appear to be about the signature or implementation of the sorting method, but about how to create one of the actual arguments to the method. — Andy Thomas
– Andy Thomas, Commented Sep 21, 2014 at 19:57

Andy Thomas · Accepted Answer · 2014-09-21 20:11:33Z

3

Note that T extends Comparable<T>. It doesn't have to be Comparable<T>.

So you could, for example, create an array of Integers, because Integer implements Comparable<Integer>.

Integer[] list = new Integer[100];
/* fill the array somehow */
Sorting.quickSort(list, 0, 99);

edited Sep 21, 2014 at 20:11

answered Sep 21, 2014 at 19:56

Andy Thomas

86.8k12 gold badges111 silver badges160 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

QuantumCop Over a year ago

Oh wow, I can't believe I didn't realize that. Is it possible to adapt this to fix the merge sort problem, though? I can't just make the new arrays within the merge sort method be Integer (or Double, etc.) arrays, because then it can't act on arbitrary types.

Andy Thomas Over a year ago

@QuantumCop - You can't create an instance of a generic array, because of type erasure - the actual generic type parameters are not available at runtime, but you would need them to create the array. So in-place sorting is easier. For mergesort, there is an ugly hack you could use for temporary arrays - create Object[]s and cast them. A cleaner option would be to use ArrayList<T>, which hides that same hack.

Andy Thomas Over a year ago

@QuantumCop - I see this is your first question. Welcome to StackOverflow! You can click the up arrow on multiple answers you find useful. You can click the checkmark outline to the left of the answer you find the most useful.

raptortech97 · Accepted Answer · 2014-09-21 20:06:49Z

0

You have to make an array of Object and then cast to an array of T. Note that this will create a compiler warning.

answered Sep 21, 2014 at 20:06

raptortech97

5073 silver badges14 bronze badges

Collectives™ on Stack Overflow

Is there a way to use Java generic types to write sorting algorithms?

2 Answers 2

3 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related