Javaでジェネリックのリストをソートするには？

Question

私はジェネリックスのソートをJavaで実装しようとしています。ここ は、抽象クラスの機能は、（Tソートするために、私の「キー」である）である：

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

    abstract public T compute(S o); 
} 

は、ここでその方法「適用」「計算」の結果に応じてリストをソートクラスプライヤー、されています

は

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; 
    } 

} 

私の質問です：このソートを行うよりスマートな方法がありますか、おそらくはバソルトではありませんか？あなたは見当違い、outputにiとjときの要素を再挿入する：あなたはバブルソートの要素を入れ替える方法に誤りがあることを

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

注：ここで もメインクラスです。また、要素を削除して再挿入する代わりに、set(index, element)を使用して前のエントリを上書きしてください。

また、2つのリストを使用してこれらのリストを同期させる代わりに、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; 
    } 
} 

もちろん、ソートはすでにJavaで実装されています。したがって、コード作成方法を学ぶ以外に、常に組み込み関数を使用する必要があります。 Comparator.comparingは（すなわち、まともなソートアルゴリズムの2nlogn回程度）の各ペアごとの比較のためのコンパレータ機能を呼び出すこと、

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

ただし：Javaの8で、それだけで一行です。その関数が計算上である場合、が高価な場合は、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

基本的には、他の配列に基づいて配列を並べ替える必要があります。値と関数の結果の両方を含むラッパーオブジェクトを導入し、それをソートすると、Collections.sortを使用することができます。

は、ここでのJava 8のストリーミング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; 
    } 

}