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.

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:http://stackoverflow.com/questions/4859261/get-the-indices-of-an-array-after-sorting — Raihan, Oct 10 '12 at 16:53
http://stackoverflow.com/questions/112234/sorting-matched-arrays-in-java — talnicolas, Oct 10 '12 at 16:54
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. — Colin D, Oct 10 '12 at 17:06

score 10 · Accepted Answer · answered Oct 10 '12 at 16:53

10

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.)

answered Oct 10 '12 at 16:53

Bill the Lizard

398,270
210
566
880

Sorting an array of objects is as efficient as sorting an array of doubles ? – Razvan Oct 10 '12 at 16:54
@Razvan Sorting an array of objects is going to be extremely efficient. I doubt you'd be able to measure the difference. – Bill the Lizard Oct 10 '12 at 16:57
1

just thought I should mention the `Comparable` interface for your new object. http://docs.oracle.com/javase/6/docs/api/java/lang/Comparable.html – Colin D Oct 10 '12 at 17:00
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. – Louis Wasserman Oct 10 '12 at 17:31

score 1 · Answer 2 · answered Oct 10 '12 at 16:54

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 :(

score 1 · Answer 3 · answered Oct 10 '12 at 16:55

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.

score 0 · Answer 4 · answered Oct 10 '12 at 16:59

Note sure what are you looking for but one other work around could be like this.

Create a map to maintain the relation between arr1 and arr2 elments

      Map<Double, Double> myLocalMap<Double, Double>();
      for(int ind=0; indx < arr1.length; indx++){
           myLocalMap.put(Double.valueOf(arr1[indx]), Double.valueOf(arr2[indx]));
      }

Now sort arr1 as you said:

     Arrays.sort(arr1);

Once arr1 is sorted, update arr2 as below:

      for(int ind=0; indx < arr1.length; indx++){
          arr2[indx] = myLocalMap.get(arr1[indx]).doubleValue();
      }

Sort array and reflect the changes in another array

4 Answers4

Linked