Skip to main content

# Feature Request: Get sorted list of indices of an array

6 replies [Last post]
edgar_holleis
Offline
Joined: 2009-06-09

The problem: Consider the following floats[]:

data[x] = 1.7 -0.3 2.1 0.5

What I want is an array of int[] that represents the order of the original array with indices.

ind[x] = 1 3 0 2
data[ind[x]] = -0.3 0.5 1.7 2.1

To my knowledge there is no way to do that easily with Java, which is a pity, since it is not much different from the usual sort(). All solutions I know of require either an excessive amount of boxing/unboxing, or a custom implementation of sort().

That would be a great addition to the class library.

## Reply viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.
carloscs
Offline
Joined: 2003-08-11

[code]
final Integer[] idx = { 0, 1, 2, 3 };
final float[] array = { 1.7f, -0.3f, 2.1f, 0.5f };

Arrays.sort(idx, new Comparator() {
@Override public int compare(final Integer o1, final Integer o2) {
return Float.compare(array[o1], array[o2]);
}
});
[/code]

edgar_holleis
Offline
Joined: 2009-06-09

Nice and elegant indeed. Unfortunately it leaves behind 2*n*log(n) pieces of garbage. That's not acceptable if you deal with big arrays (~ 10^6 elements). In the end I just did a custom implementation of Arrays.sort().

Thanks anyway

swpalmer
Offline
Joined: 2003-06-10

> To my knowledge there is no way to do that easily
> with Java

It's easy with a simple custom comparator.

Pass the data array to the comparator in it's constructor and use it to sort the index array.

The comparator will be asked to compare A and B which will effectively be ind[x] and ind[y]. But instead of comparing A and B directly, compare data[A] to data[\B] instead. That will direct the sort routine to properly order ind[] as you wish.

Message was edited by: swpalmer

mo414141
Offline
Joined: 2010-04-01

Can you please show me how to do that ?

zarr
Offline
Joined: 2008-08-24

Here is my solution:

// create SortedList
List> sortedList = SortedList_1x0.of(new ArrayList>(),
new Comparator>() {
@Override
public int compare(Pair_1x0 o1, Pair_1x0 o2) {
return o1.getFst().compareTo(o2.getFst());
}
});

// add some elements
sortedList.add(new Pair_1x0(1, -0.3F));
sortedList.add(new Pair_1x0(3, 0.5F));
sortedList.add(new Pair_1x0(0, 1.7F));
sortedList.add(new Pair_1x0(2, 2.1F));
// print sorted list
for (Pair_1x0 i : sortedList) {
System.out.print(i + ", \n");
}

I used SortedList from happy-collections https://sourceforge.net/projects/happy-guys/

edgar_holleis
Offline
Joined: 2009-06-09

I have also posted the issue on stackoverflow.com. The thread features some interessting work-arounds, some obvious, some clever. But none of the proposed solutions has quite the elegance of a new class-library function.

http://stackoverflow.com/questions/951848/