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
– jalynn2, Commented Apr 5, 2013 at 12:37
@jalynn2: Unfortunately, I have not saved the whole code that used Comparator. Please see an update of my post. — Klausos Klausos
– Klausos Klausos, Commented Apr 5, 2013 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
– eatSleepCode, Commented Apr 5, 2013 at 13:04

Community · Accepted Answer · 2017-05-23 12:03:20Z

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

Collectives™ on Stack Overflow

Sorting of two-dimensional array based on two parameters

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related