Home > Software engineering >  Sorting an ArrayList of Numbers?
Sorting an ArrayList of Numbers?

Time:02-19

I am working through Liang's Java book and one of the exercises has you implement a method to sort an ArrayList of Numbers (ArrayList<Number>). The method header looks like this:

public static void sort(ArrayList<Number> list)

I just finished implementing a shuffle method in a previous exercise for an ArrayList of Numbers (again, ArrayList<Number>) which was pretty easy and straightforward.

I'm a little confused because both the shuffle and sort exercises are marked as having the same difficulty. After getting started with the sort method however, I realised that implementing it is not trivial or as easy as the shuffle method (there is no compareTo method for Numbers). In fact, it seems I have to implement my own Comparable Interface for Numbers by checking each subclass (Integer, Double, etc...). This seems awfully tedious...

The fact that both exercises have the same difficulty suggests that I am perhaps missing some much simpler solution.

Am I off track?

CodePudding user response:

Quick answer:

public static void sort(ArrayList<Number> list) {
    list.sort(Comparator.nullsFirst(Comparator.comparingDouble(Number::doubleValue)));
}

You can check with the following input data:

public static void main(String[] args) {
    ArrayList<Number> list = new ArrayList<>(Arrays.asList(12,58,62,34,-74,25.8,214.7,1544,null,78899,-12.2));
    sort(list);
    System.out.println(list);
}

public static void sort(ArrayList<Number> list) {
    list.sort(Comparator.nullsFirst(Comparator.comparingDouble(Number::doubleValue)));
}

First checks for null values, then compares the two non-null numbers by converting them to Double, the most comprehensive numeric representation among the standard Number extensions.

It is also necessary that you are using at least version 8 of Java, as this implementation uses lambdas, which did not exist in previous versions.

CodePudding user response:

The only way I can think of doing it cleanly is to add a comparator argument which violates the required signature.

List<Number> doubleList = new ArrayList<>(List.of(10.,8.,2.,3.));

Comparator<Number> doubleComp = (a,b)->{
                              double aa = a.doubleValue();
                              double bb = b.doubleValue();
                              return aa < bb ? -1 : aa > bb ? 1 : 0;
};
                                     

sort(doubleList, doubleComp);
System.out.println(doubleList);

prints

[2.0, 3.0, 8.0, 10.0]

The sort method

public static void sort(List<Number> list, Comparator<Number> comp) {
      
      for (int i = 0; i < list.size()-1; i  ) {
          for(int k = i 1; k < list.size(); k  ) {
              if (comp.compare(list.get(i),list.get(k)) > 0) {
                  Number temp = list.get(i);
                  list.set(i, list.get(k));
                  list.set(k, temp);
              }
          }
      }
}

But a better way would be to just write a generic sort method that takes any type T that implements Comparable<T>

CodePudding user response:

You can There are many different sort algorithms and most basics are Quick Sort, Bubble Sort, Merge Sort.

I can recommend implementing Bubble Sort first. Bubble sort works by swapping adjacent elements if they're not correctly placed. Swapping repeats from the beginning of the array until all elements are in order. We know that all elements are in order when we manage to do the whole iteration without swapping at all.

public static void bubbleSort(int[] a) {
    boolean sorted = false;
    int temp;
    while(!sorted) {
        sorted = true;
        for (int i = 0; i < array.length - 1; i  ) {
            if (a[i] > a[i 1]) {
                temp = a[i];
                a[i] = a[i 1];
                a[i 1] = temp;
                sorted = false;
            }
        }
    }
}
  • Related