Блог пользователя shankysodhi

Sorting simultaneous arrays
Автор shankysodhi, 14 лет назад, По-английски
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 ...??

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
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.

→ Ответить
14 лет назад, # |
← Rev. 3   Проголосовать: нравится +3 Проголосовать: не нравится

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.


→ Ответить
14 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится
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;
}
});


→ Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
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);

→ Ответить
14 лет назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится
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
→ Ответить
  • 14 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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
    → Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    You can also use pair<pair<int,int>,int> > in C++;
    Maybe Java support something like C++ pair too
    → Ответить
    • 14 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      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?
      → Ответить
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        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
        → Ответить
      • 14 лет назад, # ^ |
        ← Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

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


        Hope, this code not consist of only errors)
        → Ответить