インデックスソート

質問

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
}

回答No.8

setter1

私も今まで知らなかった口ですが、インデックスソートとは、実体は動かさずインデックスだけをソートするもの、だそうなので、素直にこういったコードではどうでしょう。

final int[] a = { 24, 16, 12, 11, 18, 16 };

Integer[] b = new Integer[a.length];
for (int i = 0 ; i < a.length ; i++) { b[i] = i; }

Arrays.sort(b, new Comparator<Integer>() {
　public int compare(Integer o1, Integer o2) {
　　return Integer.valueOf(a[o1]).compareTo(Integer.valueOf(a[o2]));
　}
});

System.out.println(Arrays.toString(b));

実行すると

[3, 2, 1, 5, 4, 0]

です。

sortメソッドでComparatorを使えるのがオブジェクト配列だけなので、bはintではなくInteger配列にせざるを得なくなりますし、単なる連番の配列を作るだけにforループを使わなければならないのも格好悪いですが…

commons-langを使えば一応、

Integer[] b = ArrayUtils.toObject(new IntRange(0,a.length).toArray());

と、bの作成は一行で書けます。このためだけにcommons-langを追加するのは本末転倒なので、他にも使うときだけに限るでしょうけど。

お礼

＞プリミティブ配列をオブジェクト配列に変換しないでスマートに書けますか？

自己レスです。
すみません。意味不明なことを書いてしまいました。
上記の内容は、無視してください。

何を思ったかといえば、この方法と私の書いた方法とでは、
　コンパレータの実装を無名クラスで書いたか有名クラスで
　実装したかの違いしかないのでは？
と、思った次第です。

補足

なるほど、これは素直な感じです。

ところで、この方法でArrays.sort(*)に倣って
　sortIndex(byte[] a)
　sortIndex(char[] a)
　　　～
　sortIndex(double[] a)
　sortIndex(Objct[] a)
まで、全てのプリミティブ配列とオブジェクト配列までを
対象としたインデックスソートメソッドを実装するとなると、
どのようになるのでしょう。
プリミティブ配列をオブジェクト配列に変換しないでスマートに書けますか？

回答No.7

nda23

確かに重複を見落としてました。そういう場合は下記で如何でしょう。
//サンプル配列
int[] a = {24,16,12,11,18,16};
//---- ここから本体 ----
TreeMap<Integer, List<Integer>> t = new TreeMap<Integer, List<Integer>>();
for ( int i = 0 ; i < a.length ; i++ ) {
　　List<Integer> v = t.get(a[i]);
　　if ( v == null ) v = new ArrayList<Integer>();
　　v.add(i);
　　t.put(a[i],v);
}
//結果の配列
int[] r = new int[a.length];
int i = 0;
for ( Integer x : t.keySet() ) {
　　for ( Integer y : t.get(x) ) r[i++] = y;
}
//---- ここまで本体 ----

補足

これは、あまりにも。
言いにくいのですが、技巧的な上に実行効率もよくありません。

私が、N0.1の回答のところに書いたプログラムよりも、
何が優れていると思われているのでしょうか？

回答No.6

nda23

//サンプルデータ
int[] a = {24,16,12,11,18,16};
//----- ここから本体 -----
//並べ替え用TreeMap
TreeMap<Integer, Integer> t = new TreeMap<Integer, Integer>();
//値と位置（インデックス）を仕込む
for ( int i = 0 ; i < a.length ; i++ ) t.put(a[i],i);
//インデックス用の配列（★結果の配列）
int[] r = new int[a.length];
int i = 0;
//TreeMapから値順に位置（インデックス）を受け取る
for ( Integer x : t.keySet() ) r[i++] = t.get(x);
//----- ここまで本体 -----

独自にクラスを作るまでの必要は無いと思うんですけどね。

補足

インデックスソート対象の配列がユニークで無い場合、
Mapを使うと所望の結果は得られないでしょう。

そういう意味で、当初例示した配列の中に
16 を２つ入れているんですが．．．

実行して見られましたか？

回答No.5

ninoue

サンプルプログラムを作成しましたのでコンパイル実行してみてください。
record no付き、int, float, string type data sort を行っています。　

/* index sort program using java.util.Arrays.sort() routine */

import java.lang.reflect.Method;
import java.lang.System;
import java.util.Arrays;
import java.util.Comparator;

class MyObj implements Comparator {
int idx;
int age;
float height;
String name;

public MyObj(int idx, int age, float height, String name) {
this.idx=idx; this.age=age; this.height=height; this.name=name; return;
}

static void printheader() {
System.out.println(" no idx age height name");
}

static void printTitle(String titlestr) {
System.out.println(titlestr);
}

static void printmyarray(MyObj[] myarray) {
int len = myarray.length;
int i;
MyObj obj;

for (i=0; i<myarray.length; i++) {
obj = myarray[i];
if (obj != null)
obj.printmyobj(i);
}
}

void printmyobj(int no) {
System.out.printf("%5d%5d%5d%7.1f %s\n",no,idx,age,height,name);
}

// dummy routine to suppress not overrided compare(Object,Object)
public int compare(Object myobj, Object tgtobj) { return 0; }

// compare age
static Comparator ageOrder = new Comparator() {
public int compare(Object myobj, Object tgtobj) {
if (myobj==null||tgtobj==null) return 0;
MyObj mobj = (MyObj)myobj;
MyObj tobj = (MyObj)tgtobj;
if (mobj.age < tobj.age) return -1;
else if (mobj.age > tobj.age) return 1;
else return 0;
}};

// compare height
static Comparator heightOrder = new Comparator() {
public int compare(Object myobj, Object tgtobj) {
if (myobj==null||tgtobj==null) return 0;
MyObj mobj = (MyObj)myobj;
MyObj tobj = (MyObj)tgtobj;
if (mobj.height < tobj.height) return -1;
else if (mobj.height > tobj.height) return 1;
else return 0;
}};

// compare name
static Comparator nameOrder = new Comparator() {
public int compare(Object myobj, Object tgtobj) {
if (myobj==null||tgtobj==null) return 0;
MyObj mobj = (MyObj)myobj;
MyObj tobj = (MyObj)tgtobj;
return mobj.name.compareTo(tobj.name);
}};
}

public class MySort {
static Class myclass = MyObj.class;
static Method cAge;
static Method cHeight;
static Method cName;
static Object[] arglst = {Object.class, Object.class};

public static void main(String args[]) {
int nentry = 8;
MyObj[] myarray = new MyObj[nentry];
MyObj[] agearray, heightarray, namearray;

myarray[0] = new MyObj(0, 20, 169.0f, "myself");
myarray[1] = new MyObj(1, 11, 167.1f, "brother");
myarray[2] = new MyObj(2, 32, 165.2f, "sister");
myarray[3] = new MyObj(3, 64, 171.4f, "father");
myarray[4] = new MyObj(4, 63, 164.3f, "mother");

agearray = new MyObj[nentry];
heightarray = new MyObj[nentry];
namearray = new MyObj[nentry];

System.arraycopy(myarray,0,agearray,0,nentry);
System.arraycopy(myarray,0,heightarray,0,nentry);
System.arraycopy(myarray,0,namearray,0,nentry);

Arrays.sort(agearray, MyObj.ageOrder);
Arrays.sort(heightarray, MyObj.heightOrder);
Arrays.sort(namearray, MyObj.nameOrder);

MyObj.printheader();
MyObj.printTitle("original array");
MyObj.printmyarray(myarray);
MyObj.printTitle("age array");
MyObj.printmyarray(agearray);
MyObj.printTitle("height array");
MyObj.printmyarray(heightarray);
MyObj.printTitle("name array");
MyObj.printmyarray(namearray);
return;
}
}

回答No.4

ninoue

すみません。
sourceは　src.lzh でなく　src.zip として　JDKに含まれています。

回答No.3

ninoue

sunの　java standard libraryの中にsort routineが含まれています。

sample program, tutorialは　次の通り参照できます。
簡単にそのままコンパイル、コマンドラインからテストデータ入力実行が出来ます。

http://java.sun.com/javase/ja/6/docs/ja/api/
Arrays.binarySearch
Arrays.sort

http://java.sun.com/docs/books/tutorial/collections/algorithms/index.html
Algorithms: Sorting

標準library sourceは、次のJDKをdownload,installすれば install directoryにsrc.lzh
として含まれていますので、展開して参照することが出来ます。

http://java.sun.com/javase/downloads/index.jsp
Java SE Development Kit(JDK)
JDK 6 Update 16
Docs

tutorial, docs, sourceは全てdownloadすることが出来ます。
sort routine以外についても色々と役に立ちますので参照してください。

回答No.2

komi1341

質問への直接の回答ではなく、むしろ議論の範疇になりそうなので、役に立たないと思ったら無視してください。
私はインデックスソートなる機能を持つネイティブクラスがあるかどうか知りません。ただ、

> こういう基本的なアルゴリズムに関するようなクラスを
> 自力で実装する必要があるというのも気色悪いですよね．．．

この考え方に興味を持ちました。私は学生時代も含めると１０年以上、プログラミングを扱う世界にいますが、インデックスソート、というものを扱ったことも、それが必要とされる場面も知らないのです。もちろんいろいろな業界・分野がありますし、私の知識や経験が万全だとはまったく思っていないので、ご質問に対して否定的な考えは持っていません。ただ、お考えになっている機能について、必要な人がいるかもしれないなとは思うものの、基本的な機能だから標準として実装されるべきだ、とまでは思えないのです。

試しに「インデックスソート」という単語でgoogleで検索をかけてみましたが、この質問も含め600件弱しか引っかからず、有効でない結果を差し引いたらその半分もなさそうです。それらを読む限りでは主にデータベース操作に関連して使われるアルゴリズムのようですが、それより検索結果の量が気になります。この「インデックスソート」という呼び名自体は「基本的」と呼べるくらいメジャーなものなのでしょうか？　もし別の呼び名があるなら、それとjavaという検索ワードで探してみてはいかがでしょうか。
以上、少しでも参考になればと思います。

補足

＞インデックスソート、というものを扱ったことも、
＞それが必要とされる場面も知らないのです。

例えば、

　　MATLAB Function Reference
　　sort
　　http://www.mathworks.com/access/helpdesk_archive_ja_JP/r13/help/toolbox/matlab/ref/index.html?/access/helpdesk_archive_ja_JP/r13/help/toolbox/matlab/ref/sort.html&http://www.google.co.jp/search?q=matlab+sort+%E3%82%A4%E3%83%B3%E3%83%87%E3%83%83%E3%82%AF%E3%82%B9&lr=lang_ja&ie=utf-8&oe=utf-8&aq=t&rls=org.mozilla:ja:official&client=firefox-a

　　[B,INDEX] = sort(A)

こんな感じです。
戻り値が複数ある時点で、多くの人はMATLABの関数に違和感を
感じるかもしれませんが、構造体（Javaのクラス）を定義して
そのポインタ（オブジェクト）を１つ返すのと全く同等なことです。
MATLABには、実用的なライブラリが沢山存在するので、独自に
クラスを設計する場合にも、非常に有益だと思われます。

具体的な使用例としては、
　競馬のあるレースの３番人気の馬の馬体重は
　何キログラムですか？
という解を求めるプログラミングを書くとしましょう。

こんな場合に、
　オッズ配列だけをインデックスソートして、
　３番人気の馬を特定して、その馬体重を取り出す。
といった使い方をするということです。

それならば、馬構造体（オブジェクト）を馬体重をキーにして
ソートすれば良いのではと思われるかもしれませんが、
馬構造体のサイズが非常に大きいときに、最終的に必要とされない
データを含めてソートすることはヒープの無駄といえます。
また、この競馬の例では、馬番（馬名）というユニークなキーがあるので
わざわざ新たにインデックスを生成してソートすることに
無駄があるのではと思われるかもしれませんが、この方法の利点は
ユニークなキーを持っていないデータ構造でも、その中身を
一切気にせずに一意な方法でソート出来るということです。

ここまでの話では、いかにもオブジェクト指向的でないと
思われるかもしれませんが、その観点から言えば、
　オブジェクト自体を並べ替えないで、ある項目でソートした
　任意番目のオブジェクトを取り出したい
という場合にインデックスソートが威力を発揮します。
日常的に、こういう要求もあるのではないでしょうか？

＞この「インデックスソート」という呼び名自体は「基本的」と
＞呼べるくらいメジャーなものなのでしょうか？

日常的な用語の名詞結合なので、なかなか目的の内容が
探しにくくなっています。
タグソートとも言いますが、こちらもＧＵＩのタグばかりが
ヒットして大変です。
mooter検索が登場したときには検索エンジンの世界も
様変わりするかと思われましたが、全く羊頭狗肉で
使い物にならないし。

回答No.1

nda23

TreeMap じゃダメ？
http://java.sun.com/javase/ja/6/docs/ja/api/

お礼

NumberインターフェースがComparableインターフェースを
extendsしてなかったので、補足のようにIndexedNumberクラスを
書く必要があるかと思いましたが、Numberの具象クラスで
Comparableはimplementsされてました。
この不自然な仕様はなぜでしょう？

というわけで、ある程度簡略化はされましたが、自力で
こんなことを書く必要があるかどうかは、未だに疑問です。

import java.util.Arrays;

public class ArrayIndexSorter {

public static Integer[] toObject(int[] a) {
Integer[] v = new Integer[a.length];
for (int i=0, n=a.length; i<n; i++) {
v[i] = a[i];
}
return v;
}
public static Double[] toObject(double[] a) {
Double[] v = new Double[a.length];
for (int i=0, n=a.length; i<n; i++) {
v[i] = a[i];
}
return v;
}

/**
* int値の配列を数値の昇順でインデックスソート
*/
public static int[] sortIndex(int[] a) {
return sortIndex( toObject(a) );
}
/**
* double値の配列を数値の昇順でインデックスソート
*/
public static int[] sortIndex(double[] a) {
return sortIndex( toObject(a) );
}
/**
* 要素の自然順序付けに従って、指定されたオブジェクトの配列を昇順でインデックスソート
*/
public static int[] sortIndex(Object[] a) {
IndexedObject[] indexedObjects = new IndexedObject[a.length];
for (int i=0, n=a.length; i<n; i++) {
indexedObjects[i] = new IndexedObject(i, a[i]);
}
Arrays.sort(indexedObjects);
int[] b = new int[indexedObjects.length];
for (int i=0, n=b.length; i<n; i++) {
b[i] = indexedObjects[i].getIndex();
}
return b;
}

private static class IndexedObject implements Comparable<IndexedObject> {
private int index;
private Object object;
public IndexedObject(int index, Object object) {
this.index = index;
this.object = object;
}
public int getIndex() {
return index;
}
@SuppressWarnings("unchecked")
public int compareTo(IndexedObject o) {
return ((Comparable<Object>)object).compareTo(o.object);
}
}
}

補足

とりあえず、ネイティブなライブラリが見つからなかったので、
自分で書いてみましたが、本当に無いのでしょうか？

こういう基本的なアルゴリズムに関するようなクラスを
自力で実装する必要があるというのも気色悪いですよね．．．

ネイティブなライブラリの存在をご存知の方がおられましたら
ご教授ください。

import java.util.Arrays;

/**
* 配列をインデックスソートするためのクラスです。
*/
public 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]);
}
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 );
}
/**
* 要素の自然順序付けに従って、指定されたオブジェクトの配列を昇順でインデックスソートします。
*/
public static int[] sortIndex(Object[] a) {
IndexedObject[] indexedObjects = new IndexedObject[a.length];
for (int i=0, n=a.length; i<n; i++) {
indexedObjects[i] = new IndexedObject(i, a[i]);
}
return toSortedIndex( indexedObjects );
}
private static int[] toSortedIndex(Indexed[] 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 extends Indexed implements Comparable<IndexedNumber> {
private Number value;
public IndexedNumber(int index, Number value) {
this.index = index;
this.value = value;;
}
@Override
public String toString() {
return super.toString() + " [" + index + "," + value + "]";
}
public int compareTo(IndexedNumber o) {
if (o.value instanceof Long) {
return value.longValue() - o.value.longValue() > 0 ? +1 : -1;
}
return value.doubleValue() - o.value.doubleValue() > 0 ? +1 : -1;
}
}
/** インデックス付のオブジェクトを管理するクラスです。 */
private static class IndexedObject extends Indexed implements Comparable<IndexedObject> {
private Object object;
public IndexedObject(int index, Object object) {
this.index = index;
this.object = object;
}
@SuppressWarnings("unchecked")
public int compareTo(IndexedObject o) {
return ((Comparable<Object>)object).compareTo(o.object);
}
}
/** インデックス付オブジェクトのインデックスを管理するクラスです。 */
private static class Indexed {
protected int index;
public int getIndex() {
return index;
}
}

}