CODEWITHSUNDEEP
javaarrayssortingindexing
Saliya Ekanayake
Saliya Ekanayake

Reputation: 387

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

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,

Upvotes: 3

Views: 1813

Answers (7)

Masudul
Masudul

Reputation: 21981

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.

Upvotes: 1

Buhake Sindi
Buhake Sindi

Reputation: 89209

This is the how I have done it and works:

  1. Create a Key-Value pair holder class that implements Comparable.
  2. 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.

Upvotes: 0

Vishal Santharam
Vishal Santharam

Reputation: 2023

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;
    }
}

Upvotes: 1

Warren
Warren

Reputation: 76

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;
    }

}

Upvotes: 0

Boris the Spider
Boris the Spider

Reputation: 61198

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.

Upvotes: 0

yshavit
yshavit

Reputation: 43456

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

Upvotes: 0

ihsan kocak
ihsan kocak

Reputation: 1581

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)

Upvotes: 4

Related Questions