I have a long[] with its values. The thing I need is to have a sorted array that contains the indices of my first array.
For example:
INPUT:
long[ ] values = {1 , 3 , 2 , 5 , 4};
OUTPUT:
long[ ] SortIndex = {0 , 2 , 1 , 4 , 3}
which means:
values[0] < values[2] < values[1] < values[4] < values[3]
...descending or ascending order of the SortIndex is not important.
long[] values = {1 , 3 , 2 , 5 , 4};
Map<Long, Integer> indices = new HashMap<Long, Integer>();
for (int index = 0; index < values.length; index++) {
indices.put(values[index], index);
}
long[] copy = Arrays.copyOf(values, values.length);
Arrays.sort(copy);
for (int index = 0; index < copy.length; index++) {
copy[index] = indices.get(copy[index]);
}
Your list of indices will be in copy.
Working example here: http://ideone.com/A9Imz
You could do this by adding pairs of Long to a TreeMap, where the key is values[index] and the value is index.
traversing the map's iterator will yield the sortindex values.
update
Seeing that there is no accepted answer, here is the code resulting from following up the comments to this answer.
long[] values = { 1 , 3 , 2 , 5 , 4 };
int[] output = new int[values.length];
Map<Long, Integer> map = new TreeMap<Long, Integer>();
for (int n = 0; n < values.length; n++) {
map.put(values[n] * values.length + n, n);
}
int n = 0;
for (Integer index: map.values()) {
output[n++] = index;
}
System.out.println(Arrays.toString(output));
Output:
[0, 2, 1, 4, 3]
the solution also works when duplicates are part of the input:
long[] values = { 8, 5, 3, 2, 1, 1 };
Output:
[4, 5, 3, 2, 1, 0]
If it is permissible to receive the sortOrder array as an Integer array, the second loop can be replaced by:
Integer[] output = map.values().toArray(new Integer[values.length]);
sortIndex array which is your output.values[index] * values.length + index as key :-)One simplistic idea is to find the index of minimum value in each iteration and then put a large value in that index. This will work even if there are duplicates. eg:
long[] values = { 1, 3, 2, 5, 4 };
long[] indices = new long[values.length];
for (int i = 0; i < values.length; i++) {
long min = Long.MAX_VALUE;
int minIndex = 0;
for (int j = 0; j < values.length; j++) {
if (min > values[j]) {
minIndex = j;
min = values[j];
}
}
values[minIndex] = Long.MAX_VALUE;
indices[i] = minIndex;
}
System.out.println(Arrays.toString(indices));
I found another elegant solution by using the java Comparator interface. It also works when the values are not unique:
final Long[] values = { 1, 3, 2, 5, 4, 2};
Integer[] indices = new Integer[values.length];
for (int i = 0; i < indices.length; i++) {
indices[i] = i;
}
Comparator<Integer> comparator = new Comparator<Integer>() {
@Override
public int compare(Integer arg0, Integer arg1) {
return values[arg0].compareTo(values[arg1]);
}
};
Arrays.sort(indices, comparator);
System.out.println(Arrays.toString(indices));
OUTPUT:
[0, 2, 5, 1, 4, 3]
You can change the output order from ascending to descending by changing the compare order in the compare() method:
public int compare(Integer arg0, Integer arg1) {
return values[arg1].compareTo(values[arg0]);
}
You can also change the Long[] with any other comparable data type.
The most direct least complex solution would be to include an index value in the sorted objects themselves, then just populate the augmented Long object with both the long values and the original array index values, then sort. As a bonus now you have both the original long values and the indices in the same object array. You might not need to use long[] arrays at all, but only use the augmented Long classes for all long array operations.
public class LongSort implements Comparable<LongSort> {
public Long value;
public int index;
@Override public int compareTo(LongSort o) {
return this.value.compareTo(o.value);
}
}
long[] values = {1 , 3 , 2 , 5 , 4};
LongSort[] sortvalues = new LongSort[values.length];
for (int i=0;i<values.length;i++) {
sortvalues[i].value = values[i];
sortvalues[i].index = i;
}
Arrays.sort(sortvalues);
Another fully generic version of the comparator index sorter, that supports custom comparators:
public static class ObjectSort<T> implements Comparator<Integer> {
private Comparable<T>[] data;
private Comparator<T> comp;
public ObjectSort(Comparable<T>[] datai, Comparator<T> compi) {this.data=datai;this.comp=compi;}
@SuppressWarnings("unchecked")
@Override public int compare(Integer o1, Integer o2) {
int compval = -1;
if (this.comp!=null) {
compval = this.comp.compare((T)data[o1],(T)data[o2]);
} else {
compval = data[o1].compareTo((T)data[o2]);
}
return compval;
}
}
public static <T> Integer[] objectIndexSort(Comparable<T>[] data, Comparator<T> comp) {
Integer[] k = null;
if ((data!=null)&&(data.length>0)) {
Integer[] indices = new Integer[data.length];
for (int i = 0; i < indices.length; i++) {
indices[i] = i;
}
ObjectSort<T> comparator = new ObjectSort<T>(data, comp);
Arrays.sort(indices, comparator);
k = indices;
}
return k;
}
