Sort arrays of primitive types in descending order
JavaSortingJava Problem Overview
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.
The first approach that probably comes to mind is to convert it to a list of objects (boxing):
double[] array = new double[1048576];
Arrays.stream(array).boxed().sorted(Collections.reverseOrder())…
However, boxing each primitive in the array is too slow and causes a lot of GC pressure!
Another approach 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 approach is also slow - particularly if the array is already sorted quite well.
What's a better alternative?
Java Solutions
Solution 1 - Java
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;
}
Solution 2 - Java
Java Primitive includes functionality for sorting primitive arrays based on a custom comparator. Using it, and Java 8, your sample could be written as:
double[] array = new double[1048576];
...
Primitive.sort(array, (d1, d2) -> Double.compare(d2, d1), false);
If you're using Maven, you can include 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 sort, a simple edit of Java's built-in dual-pivot quicksort. This means that the speed should be close to that of built-in sorting.
Full disclosure: I wrote the Java Primitive library.
Solution 3 - Java
Heres a one-liner, using streams in Java 8
int arr = new int[]{1,2,3,4,5};
Arrays.stream(arr).boxed().sorted(Collections.reverseOrder()).mapToInt(Integer::intValue).toArray();
Solution 4 - Java
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]
Solution 5 - Java
I think the easiest solution is still:
- Getting the natural order of the array
- Finding the maximum within that sorted array which is then the last item
- 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
}
}
Solution 6 - Java
Your implementation (the one in the question) is faster than e.g. wrapping with toList() and using a comparator-based method. Auto-boxing and running through comparator methods or wrapped Collections objects is far slower than just reversing.
Of course you could write your own sort. That might not be the answer you're looking for, but note that if your comment about "if the array is already sorted quite well" happens frequently, you might do well to choose a sorting algorithm that handles that case well (e.g. insertion) rather than use Arrays.sort() (which is mergesort, or insertion if the number of elements is small).
Solution 7 - Java
There's been some confusion about Arrays.asList in the other answers. 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'll have a List with 1 element. The resulting List has the double[] array as its own element. What you want is to have a List<Double> whose elements are the elements of the double[].
Unfortunately, no solution involving Comparators will work for a primitive array. Arrays.sort only accepts a Comparator when being passed an Object[]. And for the reasons describe above, Arrays.asList won't let you make a List out of the elements of your array.
So despite my earlier answer which the comments below reference, there's no better way than manually reversing the array after sorting. Any other approach (such as copying the elements into a Double[] and reverse-sorting and copying them back) would be more code and slower.
Solution 8 - Java
You cannot use Comparators for sorting primitive arrays.
Your best bet is to implement (or borrow an implementation) of a sorting algorithm that is appropriate for your use case to sort the array (in reverse order in your case).
Solution 9 - Java
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.
Solution 10 - Java
Before sorting the given array multiply each element by -1
then use Arrays.sort(arr) then again multiply each element 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];
Solution 11 - Java
I am not aware of any primitive sorting facilities within the Java core API.
From my experimentations with the D programming language (a sort of C on steroids), I've found that the merge sort algorithm is arguably the fastest general-purpose sorting algorithm around (it's what the D language itself uses to implement its sort function).
Solution 12 - Java
Your algorithm is correct. But we can do optimization as follows: While reversing, You may try keeping another variable to reduce backward counter since computing of array.length-(i+1) may take time! And also move declaration of temp outside so that everytime it needs not 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;
}
Solution 13 - Java
If performance is important, and the list usually already is sorted quite well.
Bubble sort should be one of the slowest ways of sorting, but I have seen cases where the best performance was a simple bi-directional bubble sort.
So this may be one of the few cases where you can benefit from coding it yourself. But you really need to do it right (make sure at least somebody else confirms your code, make a proof that it works etc.)
As somebody else pointed out, it may be even better to start with a sorted array, and keep it sorted while you change the contents. That may perform even better.
Solution 14 - Java
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 was necessary
double[] b = array; // makes b point to array. so beware!
Solution 15 - Java
If using java8, just convert array to stream, sort and convert back. All of the tasks can be done just in one line, so I feel this way is not too bad.
double[] nums = Arrays.stream(nums).boxed().
.sorted((i1, i2) -> Double.compare(i2, i1))
.mapToDouble(Double::doubleValue)
.toArray();
Solution 16 - Java
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]
Solution 17 - Java
Understand it's a very old post but I stumbled upon a similar problem trying to sort primitive int arrays, so posting my solution. Suggestions/comments 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);
Solution 18 - Java
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
Solution 19 - Java
Here's a full program that sorts objects based on a inner field.
package Algorithms.BranchAndBound;
import java.util.Arrays;
import java.util.Comparator;
public class KnapSack01 {
private class ItemVals {
double weight;
double cost;
double ratio;
public ItemVals(double weight, double cost) {
this.weight = weight;
this.cost = cost;
this.ratio = weight/cost;
}
}
public ItemVals[] createSortedItemVals(double[] weight, double[] cost) {
ItemVals[] itemVals = new ItemVals[weight.length];
for(int i = 0; i < weight.length; i++) {
ItemVals itemval = new ItemVals(weight[i], cost[i]);
itemVals[i] = itemval;
}
Arrays.sort(itemVals, new Comparator<ItemVals>() {
@Override
public int compare(ItemVals o1, ItemVals o2) {
return Double.compare(o2.ratio, o1.ratio);
}
});
return itemVals;
}
public void printItemVals(ItemVals[] itemVals) {
for (int i = 0; i < itemVals.length; i++) {
System.out.println(itemVals[i].ratio);
}
}
public static void main(String[] args) {
KnapSack01 knapSack01 = new KnapSack01();
double[] weight = {2, 3.14, 1.98, 5, 3};
double[] cost = {40, 50, 100, 95, 30};
ItemVals[] itemVals = knapSack01.createSortedItemVals(weight, cost);
knapSack01.printItemVals(itemVals);
}
}
Solution 20 - Java
Double[] d = {5.5, 1.3, 8.8};
Arrays.sort(d, Collections.reverseOrder());
System.out.println(Arrays.toString(d));
Collections.reverseOrder() doesn't work on primitives, but Double, Integer etc works with Collections.reverseOrder()
Solution 21 - Java
Below is my solution, you can adapt it to your needs.
How does it work? It takes an array of integers as arguments. After that it will create a new array which will contain the same values as the array from the arguments. The reason of doing this is to leave the original array intact.
Once the new array contains the copied data, we sort it by swapping the values until the condition if(newArr[i] < newArr[i+1]) evaluates to false. That means the array is sorted in descending order.
For a thorough explanation check my blog post 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;
}
Solution 22 - Java
double[] array = new double[1048576];
...
By default order is ascending
To reverse the order
Arrays.sort(array,Collections.reverseOrder());