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?
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
double[] array = new double[1048576];
...
By default order is ascending
To reverse the order
Arrays.sort(array,Collections.reverseOrder());
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();
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).
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.
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;
}
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).
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!
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);
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.
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.
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;
}
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();
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;
}
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.
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;
}
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]
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).
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.
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.
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]
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!
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.
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);
}
}
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).
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]
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).
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()
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.
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;
}
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
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;
}
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();
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()
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).
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);
}
}
double[] array = new double[1048576];
...
By default order is ascending
To reverse the order
Arrays.sort(array,Collections.reverseOrder());
I think the easiest solution is still:
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
}
}
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];
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).
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;
}
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.
I think the easiest solution is still:
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
}
}
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);
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).
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();
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]
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;
}
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.
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];
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).
double[] array = new double[1048576];
...
By default order is ascending
To reverse the order
Arrays.sort(array,Collections.reverseOrder());
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).
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;
}
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;
}
Source: Stackoverflow.com