0

I have this piece of code and it doesn't work as expected. Can someone tell me why this doesn't sort triangles by area properly? I am looking at code for 1h and can't realize where is problem, when I run program it sorts some of it but few of them are still unsorted.

import java.util.Arrays;
import java.util.Comparator;

class Triangle {
    public final int a;
    public final int h;

    public Triangle(int a, int h) {
        this.a = a;
        this.h = h;
    }

    @Override
    public String toString() {
        return "Triangle: a = " + a + " cm and h = " + h + " cm";
    }
}

class Program {
    public static void main(String[] args) {
        Triangle[] triangles = new Triangle[] {
            new Triangle(1, 6),
            new Triangle(1, 1),
            new Triangle(1, 5),
            new Triangle(1, 8),
            new Triangle(1, 2),
            new Triangle(1, 4),
            new Triangle(1, 7),
            new Triangle(1, 9),
            new Triangle(1, 3)
        };

        System.out.println("ORIGINAL:");
        for (Triangle t : triangles) {
            System.out.println(t);
        }

        Arrays.sort(triangles, new CmpByArea());

        System.out.println();
        System.out.println("SORTED:");
        for (Triangle t : triangles) {
            System.out.println(t);
        }
    }
}

class CmpByArea implements Comparator<Triangle> {
    @Override
    public int compare(Triangle t1, Triangle t2) {
        double area1 = t1.a * t1.h / 2;
        double area2 = t2.a * t2.h / 2;
        return (int) Math.signum(area1 - area2);
    }
}
0

3 Answers 3

3

You need an only sign. So, you shouldn't divide to 2 and use double.

class CmpByArea implements Comparator<Triangle> {
    @Override
    public int compare(Triangle t1, Triangle t2) {        
        return Integer.compare(t1.a * t1.h, t2.a * t2.h);
    }
}

You can also use just lambda

Arrays.sort(triangles, (t1, t2) -> (Integer.compare(t1.a * t1.h, t2.a * t2.h)));

EDIT: As @erickson mentioned in comments, it's worth to eliminate integer overflow:

Arrays.sort(triangles, (t1, t2) -> (Integer.compare(Math.multiplyExact(t1.a,  t1.h), Math.multiplyExact(t2.a, t2.h))));
6
  • 1
    Again, use Integer.compare() to compare Integers. Using subtraction can give false results for very large absolute values, due to overflows.
    – JB Nizet
    Commented Nov 3, 2017 at 22:14
  • @JBNizet definitely makes sense. I've edited my answer.
    – dehasi
    Commented Nov 3, 2017 at 22:15
  • 2
    @JBNizet 'Using subtraction can give false results for very large absolute values' OP is using only positive values, you will never get false result by subtracting one positive integer from another it can't overflow. The multiplication can overflow though.
    – Oleg
    Commented Nov 3, 2017 at 22:21
  • 1
    @Oleg sure, but StackOverflow answers are read by many people, not necessarily realizing there might be a problem, nor when this problem can occur. Using Integer.compare() works in all cases, and is more readable than subtraction.
    – JB Nizet
    Commented Nov 3, 2017 at 22:27
  • 1
    Then you better use Math.multiplyExact() too because multiplication is more likely to overflow than subtraction.
    – erickson
    Commented Nov 3, 2017 at 22:38
1

You assign to a double but you do your calculation as integer arithmetic, which is probably not what you want.

class CmpByArea implements Comparator<Triangle> {
    @Override
    public int compare(Triangle t1, Triangle t2) {
        double area1 = (double)(t1.a) * t1.h / 2;
        double area2 = (double)(t2.a) * t2.h / 2;
        return (int) Math.signum(area1 - area2);
    }

Try converting the ints first, as above.

Remember that integer arithmatic will drop fractions. So if you have a triangle with a=1 and h=2, and another with a=1 and h=3, those both compute to 1 (2 divided by 2 is 1, and 3 divided by 2 is 1.5, rounded down to 1). So those two triangles are "the same" and might sort in the wrong order.

The trick is to convert at least one int (perferably the first one, imo) to double. Then all the ints get promoted to double, and the result is 1 and 1.5 for the example above. Now the comparison (the subtraction) works correctly to yield the desired result.

A better way to do the same thing might be, when planning on doing floating point math on a number, just store it as a double to begin with. It doesn't require conversion and also there's less chance of making a math error like this later on.

class Triangle {
    public final double a;
    public final double h;
    ...
7
  • 1
    "It would be enough to divide by 2.0, is more readable imho" Hmm, I don't think so. If the triangle's parameters are very large, you could get an integer overflow. Again, probably not the desired result.
    – markspace
    Commented Nov 3, 2017 at 22:09
  • 2
    I upvoted because it explains the bug. But comparing doubles can be done simply and safely with Double.compare(area1, area2)
    – JB Nizet
    Commented Nov 3, 2017 at 22:12
  • Ok this works but can you explain it? I dont understand why I have to explicitly convert t1.a and t2.a to double...Thanks
    – vm381
    Commented Nov 3, 2017 at 22:13
  • Right, that's what I was going for: explain the bug. But I think there are better ways to do the comparison, you're right about that.
    – markspace
    Commented Nov 3, 2017 at 22:13
  • @vm381 you're using integer division. 3/2 is 1, and 2 / 1 is 1 too. So two triangles which don't have the same area are considered equal by your comparator.
    – JB Nizet
    Commented Nov 3, 2017 at 22:15
0

There is no need to use Math.signum().

class CmpByArea implements Comparator<Triangle> {
    @Override
    public int compare(Triangle t1, Triangle t2) {
        double area1 = t1.a * t1.h / 2.0;
        double area2 = t2.a * t2.h / 2.0;
        return Double.compare(area1, area2);
    }
}

You can just compare the natural order of both areas.

In your current code, consider the cases for: new Triangle(1, 4) and new Triangle(1, 5)

area1: 1 x 4 / 2 
     = 4 / 2
     = 2

area2: 1 x 5 / 2 
     = 5 / 2
     = 2  (due to integer division)

You lost the precision for comparison, hence some of the Triangles didn't get sorted. To retain the decimal values, you can cast the operands to double or perform arithmetic with decimal values which will promote your integers to double.

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.