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

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 1

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.

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.