How to sort an array and keep track of the index in java

Question

I am trying to sort (decreasing) an array of integers but keeping track of the original index.

I mean, for example if I have this array:

b[] = { 4, 5, 3, 5, 2 }

after using Arrays.sort(b, Collections.reverseOrder()) it turns into ( I am using Arrays.sort, because in this example b is only length 5, but in my problem the length of b could be 1 < b.length < 70

b[] = { 5, 5, 4, 3, 2 }

but I want to somehow have the original index, I mean knowing that

bOrignalIndex[] = { 1, 3, 0, 2, 4 }

I don't know if my question in clear, please ask me everything. I have this piece of code in C++ that can be helpful because it does what I want

n=4
m=5
tord[] =  
[0] 0   
[1] 1   
[2] 2   
[3] 3   
ts[] =      
[0] 4   
[1] 5   
[2] 3   
[3] 5   



   tord[MAXT], ts[MAXT];
       bool ord(int a, int b){
        return ts[a] > ts[b];    }
    int main(void){
        for(int m, n; scanf("%d %d", &m, &n)){
            bool possible = true;
            FOR(i=0;i<m, i++){ // for each team
                scanf("%d", ts + i); // read team size
                tord[i] = i;
            }
            sort(tord, tord + m, ord)

The thing is after doing this, tord has the array ordered by index, that is:

tord[] =  
[0] 1   
[1] 3   
[2] 0   
[3] 2

Sounds like the [Burrows-Wheeler Transform](http://marknelson.us/1996/09/01/bwt/). — Elliott Frisch, May 10 '14 at 23:19
[Duplicate?](http://stackoverflow.com/q/4859261/645270) there are lots more like it — keyser, May 10 '14 at 23:21

score 22 · Accepted Answer · edited Mar 17 '16 at 17:00

22

Try sorting pairs of (value, index) compared by value:

public class Pair implements Comparable<Pair> {
    public final int index;
    public final int value;

    public Pair(int index, int value) {
        this.index = index;
        this.value = value;
    }

    @Override
    public int compareTo(Pair other) {
        //multiplied to -1 as the author need descending sort order
        return -1 * Integer.valueOf(this.value).compareTo(other.value);
    }
}

Then, when you're going to sort:

public static void main(String[] args) {
    Pair[] yourArray = new Pair[10];

    //fill the array
    yourArray[0] = new Pair(0, 5); yourArray[1] = new Pair(1, 10); //and so on
    Arrays.sort(yourArray);
}

Now, you have an array of Pair object ordered by value descending. Each object also contains index- the place in the original array.

P. S. I wrote the sample in Java as the question has java tag. Although, in C++ the idea is the same, only the implementation is a little bit different.

edited Mar 17 '16 at 17:00

Zack Zatkin-Gold

814
9
29

answered May 10 '14 at 23:26

Alexey Malev

6,408
4
34
52

Thank you so much for the answer :). I just implement two more method in Pair class for returning the value and the index – neteot May 11 '14 at 09:26
Is there any java8 simpler way? I need to order an array of int but in case the value is the same that one with lower index goes first. And yes I need to keep track of the original indexes. what about a map? – Enrico Giurin Aug 21 '17 at 19:53
I guess this is a simpler approach, by using Map. https://www.programcreek.com/2013/03/java-sort-map-by-value/ – Enrico Giurin Aug 21 '17 at 19:56

user3624334 · Answer 2 · 2014-05-11T01:22:39.347

The OP poster's example involved sorting an array of integer. If any of the readers have a similar situation, but with an array of non-primitive types, the following is a class that handles this for arrays of non-primitives. The class takes a somewhat different approach. It leaves the original array unmodified but instead creates an array of indexes and sorts and returns that.

public class IndirectSorter<T extends Comparable<T>> {
    public int[] sort(T args[]) {
        Integer origindex[] = new Integer[args.length];
        int retval[] = new int[args.length];
        for (int i=0; i<origindex.length; i++) {
            origindex[i] = new Integer(i);
        }
        Arrays.sort(origindex, new IndirectCompareClass<T>(args));
        for (int i=0; i<origindex.length; i++) retval[i] = origindex[i].intValue();
        return retval;
    }

    class IndirectCompareClass<T extends Comparable<T>> implements Comparator<Integer> {
        T args[];
        public IndirectCompareClass(T args[]) { this.args = args; }
        public int compare( Integer in1, Integer in2 ) {
            return args[in1.intValue()].compareTo(args[in2.intValue()]);
        }
        public boolean equals( Integer in1, Integer in2 ) {
            return args[in1.intValue()].equals(args[in2.intValue()]);
        }
    }
}

And to call it quickly you can do something like this:

public static void main(String args[] ) {
    int indexes[] = new IndirectSorter<String>().sort(args);
    for (int i : indexes) {
        System.out.printf("original pos: %d %s\n", i, args[i] );
    }
}

Edit: If you're willing to reimplement the Arrays.sort(int[]) method, you can avoid the creation and use of Integer objects. This can be appealing.

score 0 · Answer 3 · answered May 11 '14 at 05:55

The following answer provides the main steps to overcome the issue explained in the question without details code provided.

you can create custom Class that has two attributes value and index. where value is the original attribute value and index is the position before sorting.
create an ArrayList of this Class.
add the new objects of the created Class with the wanted value and index.

Note: one possible way to set the index value is to iterate through the Arraylist and set the value of index using loop index.

sort the Arraylist using specialComparable based on value attribute.

now after sorting you can know the previousindex of any entry by invoking its index attribute.

How to sort an array and keep track of the index in java

3 Answers3

Linked

Related