Sort an array based on an index array in Java (similar to C#'s Array.Sort())

Question

I am trying to find a solution in Java to do the following.

int [] keys = new int[]{7,9,4,2,8,5,6,0}; // not necessarily a continuous series
double [] vals = new double[]{10,31,20,22,21,30,33,34}; // same length as keys<br/>

I need to sort the keys (low to high) and arrange the corresponding vals in that order. For example output for this case will be,

sorted keys:   0,  2,  4,  5,  6,  7,  8,  9
ordered vals: 34, 22, 20, 33, 10, 30, 21, 31

I cannot use a map as in some computations I need to access keys and values giving an index like keys[i]or vals[j].

Thanks in advance,

Why dont you use TreeMap and insert the keys and values, with i and j, accordingly. since you said keys.length and values.length will be the same. — JNL, Aug 28 '13 at 15:40
A `TreeMap` is a `Map` and the OP said he cannot use a `Map`. — Buhake Sindi, Aug 28 '13 at 15:41
http://stackoverflow.com/questions/12824423/sort-array-and-reflect-the-changes-in-another-array — Luca Basso Ricci, Aug 28 '13 at 15:42
@BuhakeSindi The OP's reason for not using a MAP does not make much sense to me. since the length is the same for keys and values and so would be the indexes. — JNL, Aug 28 '13 at 15:42
Outside of using ihsan's answer, and the tree map, the only other option is to write sort yourself, and whenever you do a swap, also swap in the other array. — Cruncher, Aug 28 '13 at 15:50
@JNL: In the program it's required to do computations on keys and values based on their index, which is why I couldn't use a TreeMap. Could you please explain a bit on why you think it might be possible? — Saliya Ekanayake, Aug 29 '13 at 04:46

score 4 · Answer 1 · answered Aug 28 '13 at 15:39

4

Create a class including field key and value.Then implement the Comparable interface.And override the compareTo method.Stock your objects in a list and sort them like: Collections.sort(list)

answered Aug 28 '13 at 15:39

ihsan kocak

1,541
1
17
26

This would have been my solution. – Cruncher Aug 28 '13 at 15:49

Masudul · Answer 2 · 2013-08-28T16:04:37.110

You can do that with customize bubble sort. Run my code

public class IndexSort {

public static void main(String[] args) {
    int[] keys = new int[]{7, 9, 4, 2, 8, 5, 6, 0}; // not necessarily a continuous series
    double[] vals = new double[]{10, 31, 20, 22, 21, 30, 33, 34};
    for (int i = 0; i < keys.length; i++) {
        for (int j = i+1; j < keys.length; j++) {
            if(keys[i]>keys[j]){
                 int temp=keys[i];
                keys[i]=keys[j];
                keys[j]=temp;
                double t=vals[i];
                vals[i]=vals[j];
                vals[j]=t;
            }                
        }
        System.out.print(keys[i]+" -> ");
        System.out.println("  "+vals[i]);
    }
}
}

This is demo solution. For performance, you should apply this logic to other algorithm.

Note that this will be very slow for large collections as bubble sort is `O(n^2)` worst case. — Boris the Spider, Aug 28 '13 at 15:50

score 1 · Answer 3 · answered Aug 28 '13 at 15:50

You can actually create a pair and then sort like this

Pair.java

class Pair
{
int key;
double val;

Pair()
{
}
Pair(int k,double v)
{
 key=k;
 val=v;
}
}

Main.java

 class Main
    {
     public static void main(String ar[])
     {
      int [] keys = new int[]{7,9,4,2,8,5,6,0}; 
      double [] vals = new double[]{10,31,20,22,21,30,33,34};
      Pair p[]=new Pair[keys.length];   //length of any array
      for(int i=0;i<p.length;i++)
      {
         p[i] = new Pair(keys[i],vals[i]);
      }
      Collections.sort(p,new CustomComparator);
     }
    }

CustomComparator.java

public class CustomComparator implements Comparator<Pair>
   {
      public int compare(Pair a, Pair b) {  
      if (a.key > b.key) {
         return 1;
      } else if (a.key < b.key) {
         return -1;
      }
      else
      return 0;
    }
}

Your comparator can be tidied up by either using `return a.key-b.key` or, in Java 7, `Integers.compare(a.key, b.key)`. Also you cannot use `Collections.sort` with an array. — Boris the Spider, Aug 28 '13 at 15:52

score 0 · Answer 4 · answered Aug 28 '13 at 15:40

The easiest thing would probably be to first put the key/value pairs into a TreeMap, and then iterate through the Map.Entry entries of that map and re-write each key-pair. In pseudo-code:

sortedMap = new TreeMap

for i between 0 and keys.length
    sortedMap.put(keys[i], vals[i])

i = 0
for entry in sortedMap:
    keys[i] = entry.getKey()
    vals[i] = entry.getValue()
    ++i

Boris the Spider · Answer 5 · 2013-08-28T15:48:57.883

If you don't have duplicate keys (I assume you don't) then whack the whole lot into a TreeMap:

public static void main(String[] args) throws Exception {
    int[] keys = new int[]{7, 9, 4, 2, 8, 5, 6, 0};
    double[] vals = new double[]{10, 31, 20, 22, 21, 30, 33, 34};
    final Map<Integer, Double> m = new TreeMap<>();
    for (int i = 0; i < keys.length; ++i) {
        m.put(keys[i], vals[i]);
    }
    System.out.println(m);
}

Output:

{0=34.0, 2=22.0, 4=20.0, 5=30.0, 6=33.0, 7=10.0, 8=21.0, 9=31.0}
[34.0, 22.0, 20.0, 30.0, 33.0, 10.0, 21.0, 31.0]

The Collection<Double> m.values() will be ordered as you require.

Alternatively create a wrapper class around your tuples and sort a List of those:

public static void main(String[] args) throws Exception {
    int[] keys = new int[]{7, 9, 4, 2, 8, 5, 6, 0};
    double[] vals = new double[]{10, 31, 20, 22, 21, 30, 33, 34};
    final class Wrapper implements Comparable<Wrapper> {

        final int key;
        final double value;

        public Wrapper(int key, double value) {
            this.key = key;
            this.value = value;
        }

        @Override
        public int compareTo(Wrapper o) {
            return Integer.compare(key, o.key);
        }

        @Override
        public String toString() {
            return "{key=" + key + ", value=" + value + "}";
        }
    }
    final List<Wrapper> wrappers = new ArrayList<>(keys.length);
    for (int i = 0; i < keys.length; ++i) {
        wrappers.add(new Wrapper(keys[i], vals[i]));
    }
    Collections.sort(wrappers);
    System.out.println(wrappers);
}

Output:

[{key=0, value=34.0}, {key=2, value=22.0}, {key=4, value=20.0}, {key=5, value=30.0}, {key=6, value=33.0}, {key=7, value=10.0}, {key=8, value=21.0}, {key=9, value=31.0}]

Collections.sort is a stable sort so this will work with duplicates and their order will not be changed.

score 0 · Answer 6 · answered Aug 28 '13 at 15:49

The best way to do that without a map would be to swap the elements of the vals array when you also swap the values of the keys array while sorting it. For example using insertion sort:

private void insertionSort(int[] keys, int[] values){
    for(int i = 0; i < keys.length; i++){
        int key = keys[i];
        int val = values[i];
        int index = i;

        while(index > 0 && key < keys[index - 1]){
            keys[index] = keys[index - 1];
            values[index] = values[index - 1];
            index--;
        }

        keys[index] = key;
        values[index] = val;
    }

}

score 0 · Answer 7 · answered Aug 28 '13 at 15:56

This is the how I have done it and works:

Create a Key-Value pair holder class that implements Comparable.
Add your key-value pair class into a list and use Collections.sort() to sort it.

Example:

The key-value pair class:

/**
 * @author Buhake Sindi
 * @since 28 August 2013
 *
 */
public class Pair implements Comparable<Pair> {

    private int key;
    private double value;

    /**
     * @param key
     * @param value
     */
    public Pair(int key, double value) {
        super();
        this.key = key;
        this.value = value;
    }

    /**
     * @return the key
     */
    public int getKey() {
        return key;
    }

    /**
     * @return the value
     */
    public double getValue() {
        return value;
    }

    /* (non-Javadoc)
     * @see java.lang.Comparable#compareTo(java.lang.Object)
     */
    public int compareTo(Pair o) {
        // TODO Auto-generated method stub
        if (getKey() > o.getKey()) {
            return 1;
        }

        if (getKey() < o.getKey()) {
            return -1;
        }

        return 0;
    }
}

The test-case:

/**
 * @author Buhake Sindi
 * @since 28 August 2013
 *
 */
public class PairComparer {

    public static void main(String[] args) {
        List<Pair> pairs = new ArrayList<Pair>(Arrays.asList(new Pair(7, 10d),
                                         new Pair(9, 31d),
                                         new Pair(4, 20d),
                                         new Pair(2, 22d),
                                         new Pair(8, 21d),
                                         new Pair(5, 30d),
                                         new Pair(6, 33d),
                                         new Pair(0, 34d)));
        Collections.sort(pairs);
        for (Pair pair : pairs) {
            System.out.println(pair.getKey() + " - " + pair.getValue());
        }
    }
}

The output:

0 - 34.0
2 - 22.0
4 - 20.0
5 - 30.0
6 - 33.0
7 - 10.0
8 - 21.0
9 - 31.0

Hope this helps.

Sort an array based on an index array in Java (similar to C#'s Array.Sort())

7 Answers7