shankysodhi's blog

Sorting simultaneous arrays
By shankysodhi, 14 years ago, In English
Hi,

Quite a no of times when i am participating in the contests, i come across the problem where i have to sort 2 or 3 arrays according to a condition applied only on one of them .

For eg :

Cordinates of a point in 3d space are given as (x,y,z)

Now the input comes as (X[], Y[], Z[] .... are different arrays)

X[j]      Y[j]       Z[j]
j

0          7         2            1
1          3         2            5
2          4         9            2
3          5         4            3 
4          5         3            3
..          ..          ..           ..
..          ..          ..           ..
1000 terms

Now suppose i want to sort the co-ordinates in the ascending order of the x co-ordinate. Obviously i have to sort y and z accordingly too , preserving the relative position ....

Is there any easy way to do it (maybe using library function ... preferably in java).. ?? Or do i have to go for simultaneous bubble sort or some other sort every time ...??

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (11)
| Write comment?
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
I think bubble sort wont be that efficient once the N value is too high, btw i personally use C++ quicksort function under <stdlib.h> header for structure sort and it works really fine and faster, but you have to modify the code the under the sorting function according to your requirement, or you could use ur own modified any other O(nlogn) algo. I really don't know about java however.

→ Reply
14 years ago, # |
← Rev. 3   Vote: I like it +3 Vote: I do not like it

The simple way to do this is to introduce something like Point class containing all three co-ordinates and implementing Comparable interface. Then you can declare array of Points and pass it to Arrays.sort. The other way is to use index array of 0..N and custom comparator comparing x[i] and x[j] , then access x, y, and z elements via this index array. Both approaches are kind of expensive, especially the first one where many litle objects are created in the heap.


→ Reply
14 years ago, # |
  Vote: I like it +8 Vote: I do not like it
Talking about java the common practice here is to use special class to store elements of these arrays in order to have one array instead of several. Regarding the 3d points example this may look something like:

class Point {
int x, y, z;
}
...
Point[] points; // instead of x[], y[] and z[]
...
Arrays.sort(points, new Comparator<Point>() {
public int compare(Point p1, Point p2) {
return p1.x - p2.x;
}
});


→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
if you use C++, you could use STL sort whith custim struct and custom function for comparing elements:

struct point{
    int x, y;
};

bool cmp(point a, point b) {
    return a.x < b.x;
}

point a[20000];
...
and sort like this:
std::sort(a, a + n, cmp);

→ Reply
14 years ago, # |
  Vote: I like it -8 Vote: I do not like it
Thanks Darht and air !!!! .... i tried this method and it works ...:))  Not sure about the complexity though .... But it seems a lot of work .... doesnt it .... i mean to create a completely different class and then use p[i].x for the rest of the algo .... . Wondering if it is the only possible way ....???

P.S. @imslavako : m not good at c++ right now and i dont use it in most of my solution( i cant remember why ??? :) ) ... but still i will try it . thanks buddy
→ Reply
  • 14 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    It takes about 20-30 seconds to write such class, nothing hard I think.
    And if you need only 2 int coordinates, you can use java.awt.Point
    UPD: or java.awt.geom.Point2D.Double for 2 double coordinates
    → Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    You can also use pair<pair<int,int>,int> > in C++;
    Maybe Java support something like C++ pair too
    → Reply
    • 14 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      I write my own class in that case.
      But there is interface java.util.Map.Entry<K, V> and its implementation: class java.util.AbstractMap.SimpleEntry<K, V>. I don't use them because their fields are private and I don't want to call getters and setters. UPD: And key is final, and you aren't allowed to set it...

      Maybe Egor's plugin contains something like Pair?
      → Reply
      • 14 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        Hmm, Is it so hard to write it with public props if you need it.
        Pair seems to be easy.

        Anyway If you need write smth (bun not get from STL(I don't now how standard library named in Java)) write point with x/y/z it is easiest way to get this functional
        → Reply
      • 14 years ago, # ^ |
        ← Rev. 4   Vote: I like it 0 Vote: I do not like it

        Hm, maybe somethink like this will be usable for you)


        Hope, this code not consist of only errors)
        → Reply