Jessica Jessica - 2 months ago 8
Java Question

Sort a list of BigIntegers parsed from Strings , whil maitaing teh order of numbers where the values are even

I'm read in a list of strings that represent numbers in vairious fromats

I'm parsing theres numbers to BigIntegers 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 even 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.