Sort array and reflect the changes in another array

Question

I have an array of doubles, in Java : arr1 which I want to sort. Most probably the first option would be the utility method Arrays.sort(double[]).

The idea is that I want the same changes (e.g. value at index i is interchanged with value at index j in arr1) to be reflected in another array of integers: arr2 (in the sense that the values at the same indexes are changed also in arr2).

Is there a simple way (a trick) to accomplish this in Java? Or the only way is to implement the sorting algorithm by myself?

UPDATE: I see that people recommend replacing the two arrays with one array of objects containing the 2 values (one from arr1 and one from arr2). Wouldn't this bring some efficiency penalties. In other words, isn't it less efficient to sort an array of objects than an array of primitive types (doubles in this case) ?

The data is completely static. It's large (it fits in memory) but static.

Solution 1

Rather than trying to maintain sorted parallel arrays, a cleaner solution would be to create a class that encapsulates both of your data values, and just have one array of objects.

(But to answer your question, there is no built-in way to do this in Java. Implementing your own sort routine that keeps two arrays sorted based on values in one of them would work for a small amount of data that isn't likely to change, but it would be difficult to maintain.)

Solution 2

One solution which is doesn't impact the performance of sorting, ie still O(nlog(n)) time complexity.

• Use a map to store array[i] -> i
• Sort the array
• Iterate over the sorted array, and for each value, use it as a key for the map to retrieve the original index.

Edit: Raihan comment make me look miserable :(

Solution 3

Try it this way....

- Convert this array into ArrayList using the Arrays.asList()

- Create another List Object Reference Variable and assign the same ArrayList object to it, Now any changes to the first ArrayList will be reflected to the Second ArrayList.

Eg:

double[] array = new double[10];

ArrayList<Double> arList_1 = new ArrayList<Double>(Arrays.asList(array));

ArrayList<Double> arList_2 = arList2;

Now for sorting, there are 2 options:

- Use java.lang.Comparable Interface, if you want to sort it in only 1 way.

- Use java.util.Comparator Interface, if you want to sort it in more than 1 way.

Comments

[Raihan]

Have an array of indexes. Don't sort the value array, sort the index array. Then use the index array to point to both value arrays. See the solution in:stackoverflow.com/questions/4859261/…

[talnicolas]

stackoverflow.com/questions/112234/…

[Hot Licks]

This is what would be called an "external sort".

[Colin D]

To address your edit: the sort may be less efficent (metrics would be required to say for sure), but you are going to gain efficiency by not having to sort 2 arrays or have complex index mapping during value lookups.

[Razvan]

Sorting an array of objects is as efficient as sorting an array of doubles ?

[Bill the Lizard]

@Razvan Sorting an array of objects is going to be extremely efficient. I doubt you'd be able to measure the difference.

[Colin D]

just thought I should mention the Comparable interface for your new object. docs.oracle.com/javase/6/docs/api/java/lang/Comparable.html

[Louis Wasserman]

Sorting an array of objects is more efficient than building your own sort that probably won't be as smart. Those are your only options -- Java doesn't have a built-in way to propagate the changes to another array.