Sorting 1 array based on another array

Add a reference to a B object in the A object -- class A {

// the original stuff

.

.

.

// added to the A class

B assoc;

void setAssoc(B assoc) { this.assoc= assoc; }

B getAssoc() { return assoc; }

}

Now, before sorting the A array, set the associated B objects like this -- A[] a= new A[...]; // the A array

B[] b= new B[...]; // the B array

for (int i= 0; i < a.length; ++i)

a[i].setAssoc(b[i]);

Sort the A array anyway you want; every A object keeps a reference to the object B it was associated

with before the sort. You can even create a new B array -- B[] bnew= new B[ ... ];

for (int i= 0; i < a.length; ++i)

bnew[i]= a[i].getAssoc();

Does this make sense for you application?

kind regards,

Jos

JosHorsmeiera at 2007-7-16 4:42:36 >

> Assume if have an array A = [10, 8, 17, 101, 2] (Actually A contains objects of type Foo with an int key)

> And I have an array A' = [17, 8, 2] (And A' contains objects of type Bar with an int key. A subset of

> elements in A)

>

> Now I need the elements in A' re-arranged in an order determined by their order in A. So for example

the result of re-arrange(A') will be [8,17,2]. This is not a natural ordering for elements in A'.

Hrmph ... you weren't quite specific enough in your previous examples ... Am I right assuming that

because the order of those elements in A is ... 8 ... 17 ... ... 2, the elements in A' are supposed

to be rearanged to 8, 17, 2 also? If so, I understand where your O(n^2) algorithm came from.

Again an additional 'index' value can help you out -- add an index i value for every object A.

Objects in array A w.r.t. to their 8,17,2 ... etc. field. Sort array A' w.r.t. those 8,17, 2 fields acting

as a reference to those A values. All the A array elements should be stored in a SortedSet

(or anything appropriate). This reduces the big-Oh to O(n*log(n)) but it does take one sweep

over the A array to populate this ordered set.

kind regards,

Jos

JosHorsmeiera at 2007-7-16 4:42:36 >

Hi Jos:

Okay to be precise here is what I think I can do (based on your suggestion).

I can store the elements of array A in a Hashtable (their key will be the element value and the value will be the index).

So in a HT representation array A will look like:

Hash-Table for A

key value

101

8 2

17 3

1014

2 5

Now we can sort A' using any (n log n) average-case time algorithm like Quick-Sort, Heap Sort etc. but for every comparsion we will have to do a lookup in the HT for the value of the key and do the sort based on that.

I choose to use a Hash-Table because of the O(1) lookup time.

At the end i will have the array A' (of Bar objects) sorted based on A and the running time will be

O(n log n) + O(n) to build the HT + 0(1)

= 0(n log n)

Thanks for your help.

-Sam

skapoor2a at 2007-7-16 4:42:36 >

I would say it depends upon your data size as well.

If A' is relatively small in comparison to A such as a tenth the size of A, you might be paying a very large memory penalty for putting all of A in a hash set.

You could make some significant memory and speed gains by reversing the logic if the subset is small.

In the above algorithm assume | A | = n (size of A is n) and | A' | = m where m is very much < n.

Your cost is about O(n) + O(m log m) assuming O(1) for all HashSet operations. Memory is on the order of O(n) excluding the orginal data size, since you are keeping A in a HashSet that only keeps itself .75 full by default.

So I'm suggesting that you put A' in a HashMap and iterate over A doing lookups in the A' HashMap. Then as you find an element in HashMap, you take those and put them into an ArrayList of Array of type Bar. As you are iterating, you can remove elements from the A' HashMap (since you found it already) for a slight speed up and not adding any memory requirements other than the memory reqired by the A' HashMap and A' resultant ArrayList. At the end of the iteration, the elements in the ArrayList are already in the order you need (same as A).

This would result in a speed of O(n) + 2*O(m) again assuming HashMaps are O(1). The O(n) is for iterating, one of the O(m) is for putting into the HashMap and one O(m) is for putting them into the resultant Array or ArrayList. The memory would just be about 2 * O(m) leaving out the initial data parameters and depeding upon how you count the space for a HashMap with m elements vs m of those elements.

I don't know if the above helps your problem at all but it's what I've used for similar problems (usually when A and A' both contain the same type of elements).

This all probably doesn't matter since most people are not straining their CPU or memory in any way. But if you were building GB size data sets it might be a consideration. And alot of the time just writing the simplest algorithm that works in a "reasonable" amount of time is gonna have better long time payoffs in code maintainability and ease of understanding. I aggree O(n^2) is probably bad....but O(n log n) is probably close enough for most simply applications.

--zerothbase

zerothbasea at 2007-7-16 4:42:36 >