Sort arrays of primitive types in descending order

Question

I have a large array of primitive types (double). How to sort items in descending order ?

Unfortunately, the Java API does not support sorting primitive types using Comparator.

One workaround would be sorting and then the opposite:

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 - especially if the array is already sorted pretty well.

What is the best alternative?

Answer 1

Java Primitive includes functions for sorting primitive arrays based on a custom comparator. Using it and Java 8, your sample can be written as:

 double[] array = new double[1048576]; ... Primitive.sort(array, (d1, d2) -> Double.compare(d2, d1), false); 

If you are using Maven, you can enable it with:

 <dependency> <groupId>net.mintern</groupId> <artifactId>primitive</artifactId> <version>1.2.1</version> </dependency> 

When you pass false as the third argument to sort , it uses an unstable view, simple editing the built-in Java dual-pivot quick sort. This means that the speed should be close to the speed of the built-in sort.

Full disclosure: I wrote a primitive Java library.

Answer 2

I think it would be better not to reinvent the wheel and use Arrays.sort ().

Yes, I saw the "downstream" part. Sorting is the hard part, and you want to capitalize on the simplicity and speed of the Java library code. Once this is done, you will simply flip the array, which is a relatively cheap O (n) operation. Here is the code I found to do this in just 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; } 

Answer 3

Guava has methods for converting primitive arrays to wrapper type lists. The nice part is that these lists are live views, so operations on them also work with basic arrays (similar to Arrays.asList() , but for primitives).

In any case, 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 4

I think the easiest solution is still:

• Getting the natural order of an array
• Finding the maximum value inside this sorted array, which is the last element
• Using for-loop with decrement operator

As others have said: using toList is an extra effort, Arrays.sort (array, Collections.reverseOrder ()) does not work with primitives, and using additional frames seems too complicated when everything you need is already built, and therefore probably faster ...

Code example:

 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 5

Your implementation (one in the question) is faster than, for example, wrapping with toList() and using a comparator method. Automatic boxing and using comparator methods or wrapped Collection objects is much slower than just reversing.

Of course you could write your own look. This may not be the answer you are looking for, but note that if your comment about “if the array is already sorted well enough” happens often, you may need to choose a sorting algorithm that handles this case well (for example, insert ) instead of using Arrays.sort() (which is a merge or insertion if the number of elements is small).

Answer 6

Other answers had some confusion regarding Arrays.asList . If you say

 double[] arr = new double[]{6.0, 5.0, 11.0, 7.0}; List xs = Arrays.asList(arr); System.out.println(xs.size()); // prints 1 

then you will have a list with 1 element. As a result, List has a double array [] as its own element. You want to have a List<Double> whose elements are double[] elements.

Unfortunately, a solution involving comparators will not work for a primitive array. Arrays.sort only accepts a comparator when passing Object[] . And for the reasons described above, Arrays.asList will not allow you to make a List of the elements of your array.

Therefore, despite my earlier answer below, there is no better way than manually changing the array after sorting. Any other approach (for example, copying elements to double[] and reverse sorting and copying them back) will be more code and slower.

Answer 7

You cannot use Comparators to sort primitive arrays.

It is best to implement (or borrow an implementation) a sorting algorithm appropriate for your use case to sort the array (in the reverse order in your case).

Answer 8

 double[] array = new double[1048576]; 

...

By default, the order increases

To cancel the order

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

Answer 9

With numeric types, negating elements before and after sorting seems like an option. The speed with respect to one reverse after sorting depends on the cache, and if the reverse is not faster, any difference can be lost in noise.

Answer 10

 Before sorting the given array multiply each element by -1 

then use Arrays.sort (arr), then multiply each element again by -1

 for(int i=0;i<arr.length;i++) arr[i]=-arr[i]; Arrays.sort(arr); for(int i=0;i<arr.length;i++) arr[i]=-arr[i]; 

Answer 11

I am not aware of any primitive sorting options in the Java API.

From my experiments with the D programming language (a kind of C on steroids), I found that the merge sort algorithm is probably the fastest general-purpose sort algorithm (this is what the D language itself uses to implement its sort function).

• One implementation in Java
• Another implementation
• Another implementation

Answer 12

Your algorithm is correct. But we can do the optimization as follows: If the opposite is true, you can try to save another variable to decrease the count, since the calculation of array.length- (i + 1) may take some time! Also, move the time slot ad so that every time it doesn’t need to be allocated

 double temp; for(int i=0,j=array.length-1; i < (array.length/2); i++, j--) { // swap the elements temp = array[i]; array[i] = array[j]; array[j] = temp; } 

Answer 13

If performance is important and the list is usually already sorted pretty well.

Bubble should be one of the slowest sorting methods, but I have seen cases where the best performance was simple bidirectional bubble sorting.

Thus, this may be one of the few cases where you can use it yourself. But you really need to do it right (make sure that at least someone else confirms your code, make proof that it works, etc.)

As someone else noted, it might even be better to start with a sorted array and keep it sorted while you change the contents. This may work even better.

Answer 14

for small arrays this may work.

 int getOrder (double num, double[] array){ double[] b = new double[array.length]; for (int i = 0; i < array.length; i++){ b[i] = array[i]; } Arrays.sort(b); for (int i = 0; i < b.length; i++){ if ( num < b[i]) return i; } return b.length; } 

I was surprised that the initial loading of array b is necessary

 double[] b = array; // makes b point to array. so beware! 

Answer 15

If you use java8, just convert the array to stream, sort and convert back. All tasks can be performed in only one line, so I feel that this is not so bad.

 double[] nums = Arrays.stream(nums).boxed(). .sorted((i1, i2) -> Double.compare(i2, i1)) .mapToDouble(Double::doubleValue) .toArray(); 

Answer 16

Below is my solution, you can adapt it to your needs.

How it works? It takes an array of integers as arguments. After that, he will create a new array that will contain the same values ​​as the array of arguments. The reason for this is to leave the original array intact.

As soon as the new array contains the copied data, we sort it, replacing the values ​​until the condition if (newArr [i] <newArr [i + 1]) becomes false. This means that the array is sorted in descending order.

For a detailed explanation, check out my blog here .

 public static int[] sortDescending(int[] array) { int[] newArr = new int[array.length]; for(int i = 0; i < array.length; i++) { newArr[i] = array[i]; } boolean flag = true; int tempValue; while(flag) { flag = false; for(int i = 0; i < newArr.length - 1; i++) { if(newArr[i] < newArr[i+1]) { tempValue = newArr[i]; newArr[i] = newArr[i+1]; newArr[i+1] = tempValue; flag = true; } } } return newArr; } 

Answer 17

I understand this is a very old post, but I came across a similar problem, trying to sort primitive int arrays, so I post my solution. Suggestions / comments are welcome -

 int[] arr = {3,2,1,3}; List<Integer> list = new ArrayList<>(); Arrays.stream(arr).forEach(i -> list.add(i)); list.stream().sorted(Comparator.reverseOrder()).forEach(System.out::println); 

Answer 18

 double s =-1; double[] n = {111.5, 111.2, 110.5, 101.3, 101.9, 102.1, 115.2, 112.1}; for(int i = n.length-1;i>=0;--i){ int k = i-1; while(k >= 0){ if(n[i]>n[k]){ s = n[k]; n[k] = n[i]; n[i] = s; } k --; } } System.out.println(Arrays.toString(n)); it gives time complexity O(n^2) but i hope its work 

Answer 19

 Double[] d = {5.5, 1.3, 8.8}; Arrays.sort(d, Collections.reverseOrder()); System.out.println(Arrays.toString(d)); 

Collections.reverseOrder () does not work with primitives, but Double, Integer, etc. work with Collections.reverseOrder ()

Answer 20

In Java 8, a better and more concise approach might 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 will give an inverse array and be more presentable.

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

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