Sorting of two-dimensional array based on two parameters

Question

The following code performs 'hierarchical' sorting of a two-dimensional matrix. Firstly, it sorts elements based on the values of ranks. Secondly, it takes this sorted matrix, searches elements that have the same values of ranks, and sorts them based on dist. In descending order.

Question 1: Is it possible to achieve the same result in the easier way? I tried to create a Comparator, but it provided incorrect result for this particular case.

Question 2: How to get indexes of unsorted elements after sorting?

import java.util.ArrayList;

public class Test {

    public static void main(String args[]) {

        ArrayList<ArrayList<Double>> values = new ArrayList<ArrayList<Double>>();

        ArrayList<Double> ranks = new ArrayList<Double>();
        ArrayList<Double> dist = new ArrayList<Double>();

        ranks.add(8.0);
        ranks.add(3.0);
        ranks.add(8.0);
        ranks.add(1.0);

        dist.add(1.8);
        dist.add(2.8);
        dist.add(1.9);
        dist.add(2.1);

        values.add(0,ranks);
        values.add(1,dist);

        int len = ranks.size();

        ArrayList<ArrayList<Double>> sortedranks = new ArrayList<ArrayList<Double>>();

        sortedranks = order(values,0,ranks.size());

        boolean swapped = true;
        int j = 0;
        double tmp1, tmp2;
        while (swapped) {
              swapped = false;
              j++;
              for (int i = 0; i < len - j; i++) {  
                  double val1 = sortedranks.get(0).get(i);
                  double val2 = sortedranks.get(0).get(i+1);
                  if (val1==val2) {
                    if (sortedranks.get(1).get(i) < sortedranks.get(1).get(i+1)) {    
                        tmp1 = sortedranks.get(1).get(i);
                        tmp2 = sortedranks.get(1).get(i+1);
                        sortedranks.get(1).remove(i);
                        sortedranks.get(1).remove(i);
                        sortedranks.get(1).add(i,tmp2);
                        sortedranks.get(1).add(i+1,tmp1);
                        swapped = true;
                    }
                  }
              }                
        }

        for (int i = 0; i < len; i++) {
            System.out.println("Ranks " + i + " : " + sortedranks.get(0).get(i)
                    + ", Distances : " + sortedranks.get(1).get(i));
        }


    }

    public static ArrayList<ArrayList<Double>> order(ArrayList<ArrayList<Double>> values, int i_start, int i_fin) {
        boolean swapped = true;
        int j = 0;
        int i_rank = 0;
        int i_dist = 1;
        double tmp1_rank, tmp2_rank, tmp1_dist, tmp2_dist;
        while (swapped) {
              swapped = false;
              j++;
              for (int i = i_start; i < i_fin - j; i++) {                                       
                    if (values.get(i_rank).get(i) < values.get(i_rank).get(i+1)) {                          
                          tmp1_rank = values.get(i_rank).get(i);
                          tmp2_rank = values.get(i_rank).get(i+1);
                          tmp1_dist = values.get(i_dist).get(i);
                          tmp2_dist = values.get(i_dist).get(i+1);
                          values.get(i_rank).remove(i);
                          values.get(i_rank).remove(i);
                          values.get(i_dist).remove(i);
                          values.get(i_dist).remove(i);
                          values.get(i_rank).add(i,tmp2_rank);
                          values.get(i_rank).add(i+1,tmp1_rank);
                          values.get(i_dist).add(i,tmp2_dist);
                          values.get(i_dist).add(i+1,tmp1_dist);
                          swapped = true;
                    }
              }                
        }
        return values;
    }
}

The code that uses Comparator (does not work for my case):

public class MyEntry implements Comparable<MyEntry> {

    private Double rank;
    private Double dist;

    public MyEntry(double rank, double dist) {

        this.rank = rank;
        this.dist = dist;

    }

    public static Comparator<MyEntry> ValueComparator = new Comparator<MyEntry>() {

        public int compare(MyEntry value1, MyEntry value2) {

            Double rfirst = value1.rank;
            Double rsecond = value2.rank;

            Double dfirst = value1.dist;
            Double dsecond = value2.dist;

            if (rsecond != rfirst) {
                return (int) (rsecond - rfirst);
            } 
            else {
                return (int) (dsecond - dfirst);
            }

        }

    };
}

Why did your Comparator not work? I have done two-level sorts using Comparator, and they work well. Perhaps you could post that code. — jalynn2, Apr 05 '13 at 12:37
@jalynn2: Unfortunately, I have not saved the whole code that used Comparator. Please see an update of my post. — Klausos Klausos, Apr 05 '13 at 12:42
This is your result: Ranks 0 : 8.0, Distances : 1.9 Ranks 1 : 8.0, Distances : 1.8 Ranks 2 : 3.0, Distances : 2.8 Ranks 3 : 1.0, Distances : 2.1 What should be the output? — eatSleepCode, Apr 05 '13 at 13:04
@eatSleepCode: This is the correct output. In fact, my first code is correct. The problem is that it looks too complicated for such an easy task. Another problem is that my second code (Comparator) does not provide the same result as the first code. It would be nice if I can use a Comparator to achieve the results of the first code. — Klausos Klausos, Apr 05 '13 at 13:10
@Klausos Klauso : I have tried one code but i don't know how to paste it in the comment in formatted way. Its not the correct one but you can try that one. — eatSleepCode, Apr 05 '13 at 13:43

score 1 · Accepted Answer · edited May 23 '17 at 12:03

Your Comperator approach would work, but is has a few bugs. First of all I would replace the Doubles in MyEntry by double.

Comparing Double is not the same as comparing double For example:

Double a = 1.0;
Double b = 1.0;
System.out.println(a == b);
System.out.println(a.equals(b));
System.out.println(a.doubleValue()== b.doubleValue());

Will return

false
true
true

Then in the comparison you cast to int, but this implies flooring that data. (int) (2 - 1.9) will give 0 Better is to compare using < and return -1 or 1.

  public static Comparator<MyEntry> ValueComparator = new Comparator<MyEntry>() {

    public int compare(MyEntry value1, MyEntry value2) {

        double rfirst = value1.rank;
        double rsecond = value2.rank;

        double dfirst = value1.dist;
        double dsecond = value2.dist;

        if (rsecond != rfirst) {
            return rsecond < rfirst?-1:1;
        } 
        else if(dsecond!=dfirst){
            return dsecond < dfirst ?-1:1;
        }
        return 0;

    }
}

For your second question you require an index. This could be done in two ways. First option is to include the index in MyEntry like this:

 public class MyEntry implements Comparable<MyEntry> {

private double rank;
private double dist;
private int index;
private static int nextIndex = 0;

public MyEntry(double rank, double dist) {

    this.rank = rank;
    this.dist = dist;
    this.index = nextIndex++;

}

This way you will be able to retain the index but it is not so flexible.

A more flexible approach could be to have the index in a separate array, and sort that.

    class IndexedArrayComparator implements Comparator<Integer>{

    MyEntry[] array;

    public IndexedArrayComparator(MyEntry[] entries){
        this.array=entries;
    }

    public Integer[] createIndexes(){
        Integer[] index = new Integer[array.length];
        for(int i =0;i<index.length;i++){
            index[i]=i;
        }
        return index;
    }

    public int compare(Integer i0, Integer i1) {
        double rfirst = array[i0].rank;
        double rsecond = array[i1].rank;

        double dfirst = array[i0].dist;
        double dsecond = array[i1].dist;

        if (rsecond != rfirst) {
            return rsecond > rfirst?-1:1;
        } 
        else if(dsecond!=dfirst){
            return dsecond > dfirst ?-1:1;
        }
        return 0; 
    }

}

You can then use it like this:

 MyEntry[] entries = new MyEntry[5];
 entries[0]= new MyEntry(1.1,5);
 entries[1]= new MyEntry(1.1,4);
 entries[2]= new MyEntry(2.1,5);
 entries[3]= new MyEntry(0.1,3);
 entries[4]= new MyEntry(3.1,1);

 IndexedArrayComparator comp = new IndexedArrayComparator(entries);
 Integer[] index = comp.createIndexes();
 Arrays.sort(index,comp);
 for(int i =0;i<index.length;i++){
     MyEntry e = entries[index[i]];
     System.out.println(String.format("%2d:r= %3.1f, d= %3.1f" ,index[i],e.rank,e.dist));
 }

Which will give:

 3:r= 0.1, d= 3.0
 1:r= 1.1, d= 4.0
 0:r= 1.1, d= 5.0
 2:r= 2.1, d= 5.0
 4:r= 3.1, d= 1.0

The second way of sorting while maintaining the index is also described here. Credits to Jon Skeet

Sorting of two-dimensional array based on two parameters

1 Answers1