Jessica - 4 months ago 24

Java Question

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.