Sort an array of int[] via array of double[]

Question

I have an array of

double[] weights = { 32.0, 32.0, 25.0, 25.0, 30.0, 28.0,
                     12.0, 10.0,  8.0,  8.0, 18.0,  0.0 };

I want to sort its corresponding indices 0 through 11 according to a descending sort of weights:

{ 32.0, 32.0, 30.0, 28.0, 25.0, 25.0, 18.0, 12.0, 10.0, 8.0, 8.0, 0.0 }

My desired output, in this case, would be an int[]:

{ 0, 1, 4, 5, 2, 3, 10, 6, 7, 8, 9, 11 }

I have added an int[] values to keep track of indices:

int[] values = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 }

Oneliner in Scala: weights.zipWithIndex.sortBy(-_._1).map(_._2). There is a library that provides similar abstractions for Java. You can use that. — missingfaktor
– missingfaktor, Commented Dec 4, 2011 at 21:57

Evan · Accepted Answer · 2011-12-04 22:30:19Z

6

Make a comparable container class, like this

class EvanContainer implements Comparable<EvanContainer> {
    double weight;
    int value;

    EvanContainer(double w, int v) { weight = w; value = v; }

    public int compareTo(EvanContainer other) {
        return Double.compare(weight, other.weight);
    } 

}

Then you can sort that as normal.

EvanContainer[] container = new EvanContainer[weights.length];
for(int i = 0; i < weights.length; i++) {
    container[i] = new EvanContainer(weights[i],values[i]);
}

Arrays.sort(container);

edited Dec 4, 2011 at 22:30

Evan

1433 silver badges10 bronze badges

answered Dec 4, 2011 at 21:57

corsiKa

82.8k26 gold badges162 silver badges210 bronze badges

Sign up to request clarification or add additional context in comments.

6 Comments

soulcheck Over a year ago

this solution, unlike the ones using map (and not multimap) allows repeated values in the double array

Evan Over a year ago

this looks great, glowcoder. unfortunately i'm getting a printout: EvanContainer@10c832d2 EvanContainer@47808199 EvanContainer@45bc887b EvanContainer@5ca46701 EvanContainer@2d66a22b EvanContainer@2d20cc56 EvanContainer@4447393f EvanContainer@1fff7a1e EvanContainer@3daa57fb EvanContainer@7a763f5d EvanContainer@693a317a EvanContainer@6b86768e. Any idea why?

Evan Over a year ago

i believe the issue is in: container[i] = new EvanContainer(weights[i],values[i]); but i may be mistaken

corsiKa Over a year ago

@Evan the class I gave you isn't 100% complete. You'll should implement the toString() method to get a good printout like that. Something like public String toString() { return "value=" + value + " weight=" + weight; } should work.

Evan Over a year ago

that works perfectly! how can i export just the new sorted values to a new int array?

|

Tim Gee · Accepted Answer · 2011-12-07 17:31:22Z

I had this problem recently and glowcoder's answer is certainly the cleanest and simplest answer. The problem I had with that particular approach, is that it requires you to "box" every element you want to compare. Now if you have a very large number of elements in a primitive array, you don't really want to wrap every element in a object and then use Comparable to sort the wrapped objects because of the performance implications.

So I designed the following solution, which is available in Java as open-source code under the GPL here : http://open.trickl.com/trickl-sort/index.html

The sort algorithms presented allow the specification of a "Permutator". The StandardPermutator just reorders elements in an array as requested (e.g. swaps two elements at different indices). The PairedPermutator also performs the same permutation on a different array (in this case, the indices array).

This way I can use the same efficient sort algorithm on a primitive array and additionally keep track of the index rearrangement without ever boxing the values in the array. That's the theory anyway, I've not done any actual performance comparisons... Either way, I hope the library presented gives a more flexible approach to sorting.

FeifanZ · Accepted Answer · 2011-12-04 21:47:59Z

0

A Map might be a good backing structure—it keeps your values and indices in paired groups.

answered Dec 4, 2011 at 21:47

FeifanZ

16.3k8 gold badges51 silver badges88 bronze badges

Collectives™ on Stack Overflow

Sort an array of int[] via array of double[]

3 Answers 3

6 Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

6 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related