Sorting a list of Generics in Java?

Question

I'm trying to implement a sorting for Generics in Java. Here is the abstract class Function (T is my "key" in order to sort):

public abstract class Function<T extends Comparable<T>, S> {

    abstract public T compute(S o); 
}

Here is class Applier, whose method "apply" sorts the list according on the result of "compute":

import java.util.ArrayList;
import java.util.Iterator;

public class Applier<T extends Comparable<T>, S> {

    ArrayList<S> apply(ArrayList<S> input, Function<T, S> function) {
        ArrayList<T> output = new ArrayList<>(); 
        for(Iterator<S> it = input.iterator(); it.hasNext(); ){
            output.add(function.compute(it.next()));
        }
        T tmpTi, tmpTj; 
        S tmpSi, tmpSj; 
        for(int i=0; i<input.size(); i++) {
            for(int j=i+1; j<input.size(); j++) {
                if(output.get(i).compareTo(output.get(j))>0) {
                    tmpTi = output.get(i); 
                    tmpTj = output.get(j); 
                    output.remove(j); 
                    output.remove(i); 
                    output.add(i, tmpTi);
                    output.add(i, tmpTj);

                    tmpSi = input.get(i);
                    tmpSj = input.get(j);
                    input.remove(j);
                    input.remove(i);
                    input.add(i, tmpSj);
                    input.add(j, tmpSi);
                }
            }
        }
        return input; 
    }

}

My question is: is there a smarter way to do this sorting, maybe not with a bubblesort? Here is also the main class:

public static void main(String[] args) {
    Applier a = new Applier<>();
    StringLength strlen = new StringLength();

    ArrayList<String> array = new ArrayList<>();

    array.add("Hola");
    array.add("Man");
    array.add("randomstufff");
    array.add("Zerrone");
    array.add("Info3a");

    System.out.println("Order by length");
    System.out.print("before: ");
    System.out.println(array);
    a.apply(array, strlen); //works on original object
    System.out.print("After: ");
    System.out.println(array);

Answer 1

Note that there's an error in the way you swap elements in your Bubble Sort: When re-inserting the elements into output, you misplaced i and j. Also, instead of removing and re-inserting the elements, just use set(index, element) to overwrite the previous entry.

Also, instead of using two lists and keeping those lists in synch, better just use a Map.

public static class Applier<T extends Comparable<T>, S> {
    ArrayList<S> apply(ArrayList<S> input, Function<T, S> function) {
        Map<S, T> compareBy = new HashMap<>();
        for (S s : input) {
            compareBy.put(s, function.compute(s));
        }
        for(int i=0; i<input.size(); i++) {
            for(int j=i+1; j<input.size(); j++) {
                if (compareBy.get(input.get(i)).compareTo(compareBy.get(input.get(j))) > 0) {
                    S tmpS = input.get(j);
                    input.set(j, input.get(i));
                    input.set(i, tmpS);
                }
            }
        }
        return input; 
    }
}

And of course, sorting is already implemented in Java. So other than for learning how to code, you should always use the builtin functions. In Java 8, it's just a single line:

Collections.sort(array, Comparator.comparing(String::length));

Note, however, that Comparator.comparing will call the comparator function for each pairwise comparison (i.e. on the order of 2nlogn times for a decent sorting algorithm). If that function is computationally very expensive, you might want to cache it yourself, using a Map.

Map<String, Integer> compareBy = array.stream().collect(Collectors.toMap(s -> s, s -> s.length()));
Collections.sort(array, Comparator.comparing((String s) -> compareBy.get(s)));

Answer 2

Basically you want to sort an array based on some other array. You will be able to use Collections.sort if you introduce a wrapper object that contains both the values and the function results, and sort that one.

Here's a solution using Java 8 streaming API:

public class Applier<T extends Comparable<T>, S> {

    static class Wrapper<T extends Comparable<T>,S> implements Comparable<Wrapper<T,S>> {
        T key;
        S value;
        Wrapper(S s, Function<T, S> function) {
            this.key = function.compute(s);
            this.value = s;
        }
        public int compareTo(Wrapper<T,S> that) {
            return key.compareTo(that.key);
        }
    }
    ArrayList<S> apply(ArrayList<S> input, Function<T, S> function) {
        S[] sorted = (S[]) IntStream.range(0, input.size())
            .mapToObj(i -> new Wrapper<T,S>(input.get(i), function))
            .sorted()
            .map(b -> b.value).toArray();
        input.clear();
        input.addAll(Arrays.asList(sorted));
        return input;
    }

}