Jessica Jessica - 2 months ago 17
Java Question

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

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;
}
}

Answer

The problem is that the selection sort algorithm you're using is not stable. That is, it doesn't sure 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.

Insertion sort and bubble sort are stable algorithms, which maintain the relative order of equal items. I would suggest using one of those two algorithms in place of your selection sort.