インデックスソート

質問

Javaに、インデックスソートを実行するライブラリーはありますか？

例えば、
　{24,16,12,11,18,16}
の入力に対して、昇順ソートしたときのインデックス位置
　{3,2,1,5,4,0}
を出力してくれるようなライブラリを探しています。

どなたか、ご存じないでしょうか？
以上、よろしくお願いいたします。

回答No.9

hrm_mmm

インデックスソートの意味がどうにも解りにくく様子をみてましたが回答８を読んで納得です。
人のアイデアで勝負みたいになりますが、回答８のルーチンを汎用化してみました、Comparableを実装したクラスの配列なら何でもokです。
しかし、primitive型は、、、ラッパー型に変換してからMySortUtil.sortIndex(final Comparable[] a)を呼ぶか、MySortUtil.sortIndexの方に、それぞれの型の引数を取るメソッドを作るか、、、さてどっちがいいだろう？ってユーザーにしてみれば、メソッドオーバーロードしてある方がいいに決まってますよね。
それから返り値型はint[] に変換した方がいいのだろうか？？？
以下長文失礼します。
/* java 5 でcompile */
import java.util.Comparator;
import java.util.Arrays;
public class SortTest {
public static void main(String[] args) {
Integer[] b;
Integer[] aa = { 24, 16, 12, 11, 18, 16 };
b = MySortUtil.sortIndex(aa);
System.out.println("元" + Arrays.toString(aa));
System.out.println("index sorted"+Arrays.toString(b));
Character[] cc = {'b', 'k','a','z','b'};
b = MySortUtil.sortIndex(cc);
System.out.println("元" + Arrays.toString(cc));
System.out.println("index sorted"+Arrays.toString(b));
byte[] bb = {'f', 'b','a','z','b'};
b = MySortUtil.sortIndex(bb);
System.out.println("元" + Arrays.toString(bb));
System.out.println("index sorted"+Arrays.toString(b));

int[] bp;
double[] dp = {1.0, 11.99, 98.098, 0.999, 6.09};
Double[] dw = new Double[dp.length] ;
for(int i=0; i<dp.length; i++){dw[i]=Double.valueOf(dp[i]);}
System.out.println("元" + Arrays.toString(dp));
b = MySortUtil.sortIndex(dw); /* double[] 用のメソッドをまだ書いてないのでDouble[]型の方のみ */
System.out.println("index sorted"+Arrays.toString(b));
bp = ArrayIndexSorter.sortIndex(dp); /* 書き換え版 ArrayIndexSorter */
System.out.println("index sorted2:"+Arrays.toString(bp));
bp = ArrayIndexSorter.sortIndex(dw);
System.out.println("index sorted3:"+Arrays.toString(bp));
}
}
class MySortUtil{
public static Integer[] sortIndex(final Comparable[] a){
Integer[] b = new Integer[a.length];
for (int i = 0 ; i < a.length ; i++) { b[i] = i; }
Arrays.sort(b, new Comparator<Integer>() {
@SuppressWarnings("unchecked") // この行がないとwarningがでる
public int compare(Integer o1, Integer o2) {
return a[o1].compareTo( a[o2]);
}
});
return b;
}
/* byte[]引数のものだけ作ってみた、あとはコピー＆ペーストして、引数のbyte[]と比較用Byteの型を各型に置き換えればできあがりではある。*/
public static Integer[] sortIndex(final byte[] a){
Integer[] b = new Integer[a.length];
for (int i = 0 ; i < a.length ; i++) { b[i] = i; }
Arrays.sort(b, new Comparator<Integer>() {
@SuppressWarnings("unchecked")
public int compare(Integer o1, Integer o2) {
return Byte.valueOf(a[o1]).compareTo( Byte.valueOf(a[o2]) );
/* 直接引き算して、とも思ったが範囲外エラーが出ては困るので、やはり、ラッパー型でcompareToを使うのがよいようです。*/
}
});
return b;
}
}
/*
＞コンパレータの実装を無名クラスで書いたか有名クラスで実装したかの違い
これについては、インラインで書くことによって、メソッド内の変数を使って直接比較できる＝新たなobject作成時間節約ということが利点。
逆にprimitive型毎に無名コンパレータがたくさんできてしまうということでもあるけど。
No1の補足に記述されたクラスですが、innerクラスを３つも作らなくてもいいのではって思ったのと、NumberじゃなくてComparable型でvalueを保持すればcompareToメソッドが使えるのと、自作のComparable実装クラスの配列でもこのソートが出来るようになるので、以下のようにしてみました。
*/
/**
* 配列をインデックスソートするためのクラスです。
* ※マークで変更部分を説明
*/
class ArrayIndexSorter {
/**
* 指定された byte値の配列を数値の昇順でインデックスソートします。
*/
public static int[] sortIndex(byte[] a) {
IndexedNumber[] indexedNumbers = new IndexedNumber[a.length];
for (int i=0, n=a.length; i<n; i++) {
indexedNumbers[i] = new IndexedNumber(i, a[i]);
}
return toSortedIndex( indexedNumbers );
}
/**
* 指定された int値の配列を数値の昇順でインデックスソートします。
*/
public static int[] sortIndex(int[] a) {
IndexedNumber[] indexedNumbers = new IndexedNumber[a.length];
for (int i=0, n=a.length; i<n; i++) {
indexedNumbers[i] = new IndexedNumber(i, a[i]);
/* ※配列全体でなければ、 Comparable value =1; も問題なく代入できる */
}
return toSortedIndex( indexedNumbers );
}
/**
* 指定された long値の配列を数値の昇順でインデックスソートします。
*/
public static int[] sortIndex(long[] a) {
IndexedNumber[] indexedNumbers = new IndexedNumber[a.length];
for (int i=0, n=a.length; i<n; i++) {
indexedNumbers[i] = new IndexedNumber(i, a[i]);
}
return toSortedIndex( indexedNumbers );
}
/**
* 指定された float値の配列を数値の昇順でインデックスソートします。
*/
public static int[] sortIndex(float[] a) {
IndexedNumber[] indexedNumbers = new IndexedNumber[a.length];
for (int i=0, n=a.length; i<n; i++) {
indexedNumbers[i] = new IndexedNumber(i, a[i]);
}
return toSortedIndex( indexedNumbers );
}
/**
* 指定された double値の配列を数値の昇順でインデックスソートします。
*/
public static int[] sortIndex(double[] a) {
IndexedNumber[] indexedNumbers = new IndexedNumber[a.length];
for (int i=0, n=a.length; i<n; i++) {
indexedNumbers[i] = new IndexedNumber(i, a[i]);
}
return toSortedIndex( indexedNumbers );
}
/**
* 要素の自然順序付けに従って、指定されたオブジェクトの配列を昇順でインデックスソートします。
* ※どのみちComparableを実装してないとソートできないのだから、Comparable[] 型で受け取りましょう
*/
public static int[] sortIndex(Comparable[] a) {
IndexedNumber[] indexedObjects = new IndexedNumber[a.length];
for (int i=0, n=a.length; i<n; i++) {
indexedObjects[i] = new IndexedNumber(i, a[i]);
}
return toSortedIndex( indexedObjects );
}
private static int[] toSortedIndex(IndexedNumber[] indexed) {
Arrays.sort(indexed);
int[] b = new int[indexed.length];
for (int i=0, n=b.length; i<n; i++) {
b[i] = indexed[i].getIndex();
}
return b;
}

/** インデックス付の値を管理するクラスです。 */
private static class IndexedNumber implements Comparable<IndexedNumber> {
private Comparable value; /* ※NumberがComparableではないので、Comparable型にする */
private int index; /* ※IndexedObject もIndexedNumberで共通処理できるようになるとIndexedクラスの必要性も無くなる */
int getIndex() {
return index;
}
/* ※Comparable型にすれば、Object[] 用のクラスを別にする必要がない */
public IndexedNumber(int index, Comparable value) {
this.index = index;
this.value = value;;
}
@Override
public String toString() {
return super.toString() + " [" + index + "," + value + "]";
}
public int compareTo(IndexedNumber o) {
return value.compareTo( o.value) ;
}
} // inner class end
}