Big Decimal Comparison in Java

Question

Is that a problem with BigDecimal comparison or the expected output in wrong?

import java.math.*;
import java.util.*;
class Solution{

 public static void main(String []argh)
 {

    int res;
    String temp = "";
    Scanner sc= new Scanner(System.in);
    MathContext mc = new MathContext(100, RoundingMode.FLOOR);
    int n=sc.nextInt();
    String []s=new String[n+2];
    for(int i=0;i<n;i++)
    {
        s[i]=sc.next();
    }

    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            res = new BigDecimal(s[i], mc).compareTo(new BigDecimal(s[j], mc));
            if(res == 1){
                temp = s[i];
                s[i] = s[j];
                s[j] = temp;
            }
        }
    }

    for(int i=0;i<n;i++)
    {
        System.out.println(s[i]);
    }

 }
}

Sample Input:     9 -100 50 0 56.6 90 0.12 .12 02.34 000.000

Expected Output: 90 56.6 50 02.34 0.12 .12 0 000.000 -100

My Output:       90 56.6 50 02.34 .12 0.12 0 000.000 -100

Answer 1

You need to implement this code in order to preserve ordering of equivalent terms. With normal sorting algorithms you can sort successfully but will fail to preserve order of sorting of .12 and 0.12

Here is your code to get exact expected result:

java.math.BigDecimal;
import java.util.*;
class Solution{
    public static void main(String []args){
        //Input
        Scanner sc= new Scanner(System.in);
        int n=sc.nextInt();
        String []s=new String[n+2];
        for(int i=0;i<n;i++){
            s[i]=sc.next();
        }
        sc.close();

        Comparator<String> customComparator = new Comparator<String>() {
        @Override
        public int compare(String s1, String s2) {
            BigDecimal a = new BigDecimal(s1);
            BigDecimal b = new BigDecimal(s2);
            return b.compareTo(a); 
        }
        };

        Arrays.sort(s, 0, n, customComparator);


        //Output
        for(int i=0;i<n;i++)
        {
            System.out.println(s[i]);
        }
   }
}

Answer 2

In your method, each element which are not the biggest element in the rest of the array may also be swapped.

For example, in the second round inner loop, when i = 0, and j = 1.

s[i] = -100 
s[j] = 50

then s[I] and s[j] swap with each other.

Actually, s[j] = 50 is not the biggest element in the rest of the array. But the position of the element will be changed, thus the original order is also be changed.

In order to keep the original position of each element, you should only swap the biggest element of the rest of the array. These are not the biggest element should not be swapped during each iteration

Here is an example code

class Solution{
    public static void main(String []args){
        //Input
        Scanner sc= new Scanner(System.in);
        int n=sc.nextInt();
        String []s=new String[n+2];
        for(int i=0;i<n;i++){
            s[i]=sc.next();
        }
        sc.close();

        // position of the biggest element in the array
        // it is used as a mark, we will use it later 
        // when we put the biggest element in the front of the array
           int maxIndex;

        for (int i = 0; i < n; i++) {
            // at the begin of a loop, 
            // set the first element as the biggest element
            // the maxDec may be changed during each iteration
            String maxDec = s[i];

            // reset maxDec at each iteration
            maxIndex = i;

            // we always put the biggest element in the front of the array
            // we only changed the position of the biggest element
            // other elements which are not the biggest 
            // will keep the same position as before
            for (int j = i; j < n; j++) {
                // create two BigDecimal objects for comparasion
                BigDecimal max = new BigDecimal(maxDec);
                BigDecimal dec = new BigDecimal(s[j]);

                // if two decimal are equal
                if (max.compareTo(dec) == 0) 
                    continue;

                // if any element greater the maxDec
                // mark it position, 
                // but does not put it in the front of the array
                // this operation will keep 
                // the original order of element in the array
                if (max.compareTo(dec) < 0) {
                    maxDec = s[j];
                    maxIndex = j;
                }
            }

            // in the end of loop, 
            // maxIndex marks the position of the biggest element
            // we put it in the front of the array
            if (i != maxIndex) {
                s[maxIndex] = s[i];
                s[i] = maxDec;
            }
        }

        for(int i=0;i<n;i++)
        {
            System.out.println(s[i]);
        }
    }
}

Answer 3

Your sorting algorithm doesn't preserve the position of equivalent items. This causes the output to be different from what you are expecting.

If you want items that are "equivalent" to remain in the same order as they were entered, you will need to implement that sorting algorithm.

Here is your code updated to sort in the fashion expected:

class Solution {

    public static void main(String[] argh) {

        int res;
        String temp = "";
        Scanner sc = new Scanner(System.in);
        MathContext mc = new MathContext(100, RoundingMode.FLOOR);

        int n = sc.nextInt();
        String[] s = new String[n + 2];

        for (int i = 0; i < n; i++) {
            s[i] = sc.next();
        }

        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                res = new BigDecimal(s[j + 0], mc).compareTo(new BigDecimal(s[j + 1], mc));
                if (res == -1) {
                    temp = s[j + 1];
                    s[j + 1] = s[j + 0];
                    s[j + 0] = temp;
                }
            }
        }

        for (int i = 0; i < n; i++) {
            System.out.println(s[i]);
        }

        sc.close();
    }
}

Answer 4

That is all because of the order of comparison

Your algorithm is copying bigger value to the left. Lets consider state of string array after every iteration. When i=0 array will be:

i=0: -100 50 0 56.6 90 0.12 .12 02.34 000.000

because -100 is minimal it is stay on its place. Go ahead:

i=1: 50 -100 0 56.6 90 0.12 .12 02.34 000.000 

because 50 is bigger than -100 it will be copied to the left. Go ahead:

i=2: 50 0 -100 56.6 90 0.12 .12 02.34 000.000 
i=3: 56.6 50 0 -100 90 0.12 .12 02.34 000.000 
i=4: 90 56.6 50 0 -100 0.12 .12 02.34 000.000 

The thing, you're interested in will be happened when i=5 and s[5] is 0.12:

i=5: 90 56.6 50 0.12 0 -100 .12 02.34 000.000 

0.12 will be compared earlier than .12, and will take its place before 0. Now, when i=6 we will compare .12:

i=6: 90 56.6 50 0.12 .12 0 -100 02.34 000.000

Because the .12 is not bigger that 0.12 and it is compared later than 0.12 it will stay on right side of 0.12.

So, there is not problem with BigDecimal comparison. It is working proper way.

Hope my explanation is not too much complicated.