Sort arrays of primitive types in descending order

Question

I've got a large array of primitive types (double). How do I sort the elements in descending order?

Unfortunately the Java API doesn't support sorting of primitive types with a Comparator.

One workaround would be to sort and then reverse:

double[] array = new double[1048576];
...
Arrays.sort(array);
// reverse the array
for (int i = 0; i < array.length / 2; i++) {
     // swap the elements
     double temp = array[i];
     array[i] = array[array.length - (i + 1)];
     array[array.length - (i + 1)] = temp;
}

This is slow - particularly if the array is already sorted quite well.

What's a better alternative?

Answer 1

I think the easiest solution is still:

1. Getting the natural order of the array
2. Finding the maximum within that sorted array which is then the last item
3. Using a for-loop with decrement operator

As said by others before: using toList is additional effort, Arrays.sort(array,Collections.reverseOrder()) doesn't work with primitives and using an extra framework seems too complicated when all you need is already inbuild and therefore probably faster as well...

Sample code:

import java.util.Arrays;

public class SimpleDescending {

    public static void main(String[] args) {

        // unsorted array
        int[] integerList = {55, 44, 33, 88, 99};

        // Getting the natural (ascending) order of the array
        Arrays.sort(integerList);

        // Getting the last item of the now sorted array (which represents the maximum, in other words: highest number)
        int max = integerList.length-1;

        // reversing the order with a simple for-loop
        System.out.println("Array in descending order:");
        for(int i=max; i>=0; i--) {
            System.out.println(integerList[i]);
        }

        // You could make the code even shorter skipping the variable max and use
        // "int i=integerList.length-1" instead of int "i=max" in the parentheses of the for-loop
    }
}

Answer 2

Guava has methods for converting primitive arrays to Lists of wrapper types. The nice part is that these lists are live views, so operations on them work on the underlying arrays as well (similar to Arrays.asList(), but for primitives).

Anyway, each of these Lists can be passed to Collections.reverse():

int[] intArr = { 1, 2, 3, 4, 5 };
float[] floatArr = { 1.0f, 2.0f, 3.0f, 4.0f, 5.0f };
double[] doubleArr = { 1.0d, 2.0d, 3.0d, 4.0d, 5.0d };
byte[] byteArr = { 1, 2, 3, 4, 5 };
short[] shortArr = { 1, 2, 3, 4, 5 };
Collections.reverse(Ints.asList(intArr));
Collections.reverse(Floats.asList(floatArr));
Collections.reverse(Doubles.asList(doubleArr));
Collections.reverse(Bytes.asList(byteArr));
Collections.reverse(Shorts.asList(shortArr));
System.out.println(Arrays.toString(intArr));
System.out.println(Arrays.toString(floatArr));
System.out.println(Arrays.toString(doubleArr));
System.out.println(Arrays.toString(byteArr));
System.out.println(Arrays.toString(shortArr));

Output:

[5, 4, 3, 2, 1]
[5.0, 4.0, 3.0, 2.0, 1.0]
[5.0, 4.0, 3.0, 2.0, 1.0]
[5, 4, 3, 2, 1]
[5, 4, 3, 2, 1]

Answer 3

double[] array = new double[1048576];

...

By default order is ascending

To reverse the order

Arrays.sort(array,Collections.reverseOrder());

Answer 4

With numerical types, negating the elements before and after sort seems an option. Speed relative to a single reverse after sort depends on cache, and if reverse is not faster, any difference may well be lost in noise.

Answer 5

In Java 8, a better and more concise approach could be:

double[] arr = {13.6, 7.2, 6.02, 45.8, 21.09, 9.12, 2.53, 100.4};

Double[] boxedarr = Arrays.stream( arr ).boxed().toArray( Double[]::new );
Arrays.sort(boxedarr, Collections.reverseOrder());
System.out.println(Arrays.toString(boxedarr));

This would give the reversed array and is more presentable.

Input: [13.6, 7.2, 6.02, 45.8, 21.09, 9.12, 2.53, 100.4]

Output: [100.4, 45.8, 21.09, 13.6, 9.12, 7.2, 6.02, 2.53]

Answer 6

I think it would be best not to re-invent the wheel and use Arrays.sort().

Yes, I saw the "descending" part. The sorting is the hard part, and you want to benefit from the simplicity and speed of Java's library code. Once that's done, you simply reverse the array, which is a relatively cheap O(n) operation. Here's some code I found to do this in as little as 4 lines:

for (int left=0, right=b.length-1; left<right; left++, right--) {
    // exchange the first and last
    int temp = b[left]; b[left]  = b[right]; b[right] = temp;
}