インデックスソート(1/2)

インデックスソートの意味がどうにも解りにくく様子をみてましたが回答８を読んで納得です。
人のアイデアで勝負みたいになりますが、回答８のルーチンを汎用化してみました、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
}

投稿日時 - 2009-10-18 02:11:36

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

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を追加するのは本末転倒なので、他にも使うときだけに限るでしょうけど。

投稿日時 - 2009-10-15 21:07:19

確かに重複を見落としてました。そういう場合は下記で如何でしょう。
//サンプル配列
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;
}
//---- ここまで本体 ----

投稿日時 - 2009-10-14 16:36:03

//サンプルデータ
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);
//----- ここまで本体 -----

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

投稿日時 - 2009-10-14 11:26:32

サンプルプログラムを作成しましたのでコンパイル実行してみてください。
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;
}
}

投稿日時 - 2009-10-14 10:14:26