How can I convert this sorting method to be generic in Java?

Question

This question is kind of long... so bear with me please.

I have to convert a SelectionSort method that was covered in my book that was built to sort arrays, and make it generic so that I can enter either doubles or ints into it and have it work.

It doesn't seem to allow generic arrays, so I'm attempting to use an ArrayList. The problem here is since the int and doubles are now in Integer and Double wrappers, it breaks the SelectionSort method.

I've attempted to fix it, but I'm having no luck. I'll post the original SelectionSort method below, and then the class and driver that I'm creating.

Original SelectionSort:

public class SelectionSort {
private int[] data;
private static final Random generator = new Random();

public SelectionSort(int size) {
    data = new int[size];

    for(int i = 0; i < size; i++) {
        data[i] = 10 + generator.nextInt(90);
    }
}

public void sort() {
    int smallest;

    for(int i = 0; i < data.length - 1; i++) {
        smallest = i;

        for(int index = i + 1; index < data.length; index++) {
            if(data[index] < data[smallest]) {
                smallest = index;
            }
        }

        swap(i, smallest);
    }
}

public void swap(int first, int second) {
    int temporary = data[first];
    data[first] = data[second];
    data[second] = temporary;
}

}

My simple driver program:

public class GenericsDriver {

public static void main(String[] args) {

    SelectionSort<Integer> intSort = new SelectionSort<Integer>();

    intSort.AddGrade(100);
    intSort.AddGrade(90);
    intSort.AddGrade(50);
    intSort.AddGrade(80);
    intSort.AddGrade(95);

    intSort.PrintNumbers();

    //sort here

    intSort.PrintNumbers();

    SelectionSort<Double> doubleSort = new SelectionSort<Double>();

    doubleSort.AddGrade(100.1);
    doubleSort.AddGrade(90.4);
    doubleSort.AddGrade(50.7);
    doubleSort.AddGrade(100.2);
    doubleSort.AddGrade(100.5);

    doubleSort.PrintNumbers();

    //sort here

    doubleSort.PrintNumbers();

}

}

The new class and my attempt to repurpose the SelectionSort method:

import java.util.*;

public class SelectionSort <T> {

private Array<T> numbers;

public SelectionSort() {
    numbers = new ArrayList<T>();
}

public void AddGrade(T number) {
    numbers.add(number);
}

public void PrintNumbers() {
    System.out.println(numbers.toString());

}

public <T extends Comparable<T>> selectionSort() {
    int smallest;

    for(int  i = 0; i < numbers.size(); i++) {
        smallest = i;

        for(int index = i + 1; index < numbers.size(); index++) {
            if(numbers.) {
            //I've tried everything here...
                            //from using number.get(index), and everything else
                            //I could think of
            }
        }
    }
}

public void swap(int first, int second) {

}

}

As you can see... I haven't had any luck with sort or swap within my new class. I can't get it to work. My instructions have a hint that I should use > in my sort method...but nothing is giving me the ability to use a .compareTo() method.

This is the actual directive from my book: Write a generic method selectionSort based on the sort program of Fig 19.6 and 19.7 (That's the code I gave above). Write a test program that inputs, sorts and outputs an Integer array and a Float array. Hint: Use > in the type-parameter section for method selectionSort, so that you can use method compareTo() to compare the objects of the type that T represents.

Could someone please give me some guidance here? Thanks.

Answer 1

It seems that you are new to generics. If you want the program to be the way you wrote it, I can point out few mistakes, which you can improve and then try running your program.

In the third code listing where you defined the class as

SelectionSort <T>

The declaration

private Array<T> numbers; 

is incorrect because you do not want this Array class, you can instead use the following:

private List<T> numbers; 

Also, there is no point declaring the new selectionSort() generic method as

public <T extends Comparable<T>> selectionSort() {

Do you seriously want a Comparable or its sub class to be the return type? No, you want a List of T to be returned as an output of the selection Sort process.

Please get back if you still have any doubts.

Happy to Help Dharam

Answer 2

Use a comparator. This SO answer has some details. You can use the same concept to define your own comparators. That way your sorting algorithm is truly generic and can handle any data type (complex numbers for example)

Answer 3

A quick peek at the javadocs (http://docs.oracle.com/javase/1.4.2/docs/api/java/lang/Double.html ) shows that Double implements the Comparable interface, which means that it will have a compareTo() method.

The point that your book is trying to force you to get your head around is the concept that you can have multiple types (Integer, Double) that implement the same interface (Comparable), and that you can take advantage of that in your code.

So:

Double firstDouble = Double.valueof(42.0); Double secondDouble = Double.valueof(43.0);

Integer firstInteger = Integer.valueof(42); Integer secondInteger = Integer.valueof(43);

so you could write: firstDouble.compareTo(secondDouble) and firstInteger.compareTo(secondInteger) - but by implementing your sort on Comparable (instead of Integer, Double, etc...), you can just use:

numbers.get(i).compareTo(numbers.get(i+1));

hth