Jessica - 1 year ago 64
Java Question

# Sort a list of BigDecimals parsed from Strings, while maintainig the order of numbers where the values are equal

I'm read in a list of strings that represent numbers in various formats

I'm parsing these numbers to BigDecimals and sorting them.

I then print the numbers back out in their original format.

The problem is that I need to maintain the ordering of numbers that are equal which is not happening in my current code.

``````import 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(); for (int i = 0; i < n -1; i++) {
for (int k = (i + 1); k < n; k++) {
if (new BigDecimal(s[i]).compareTo(new BigDecimal(s[k])) < 0) {
String tempValue = s[i];
s[i] = s[k];
s[k] = tempValue;
}
}
}
``````

Input

``````9
-100
50
0
56.6
90
0.12
.12
02.34
000.000
``````

Output

``````90
56.6
50
02.34
.12
0.12  (Wrong order here)
0
000.000
-100
``````

Expected Output

``````90
56.6
50
02.34
0.12
.12
0
000.000
-100
``````

Solution

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

The problem is that the selection sort algorithm you're using is not stable. That is, it doesn't ensure that items with equal value maintain their relative order in the list. Consider this simple list of items: `[5.0, 5, 3, 6]`.
If you want to sort that in descending order, then after the first pass of selection sort, you'll have: `[6, 5, 3, 5.0]`. The `5.0` got swapped with `6`. The items `5.0` and `5` are now out of order, and they'll stay that way.