CODEWITHSUNDEEP
csorting
muddytu
muddytu

Reputation: 17

plane coordinate point sorting

we have a group of coordinate points (x,y) and they are int.

how can I sort it by x coordinate and then print all the coordinate points.

We use two arrays to store the coordinate points respectively.

That's x[0] x[1]...x[n-1]

y[0] y[1]...y[n-1]

and (x[0] y[0]) (x[1] y[1])...(x[n-1] y[n-1]) are the coordinate points which we need to sort.

the problem is that when I use a sorting algorithm to sort the array x[0] x[1]...x[n-1], the result is a new sorted array x[0] x[1]...x[n-1], and I cannot know the corresponding y in the sorted array x[0] x[1]...x[n-1].

Please tell me how can I deal with it? Can I use another way to store the coordinate points?

Upvotes: 0

Views: 2321

Answers (5)

AshokSharma842
AshokSharma842

Reputation: 11

While comparing, compare only x array values, but while swapping, swap both array values,

if(x[i] > x[j]){
    swap(x[i],x[j])
    swap(y[i],y[j])
}

Upvotes: 0

shawon
shawon

Reputation: 1022

At first Sort Points According to x co-ordinate, then if there are same x co-ordinate sort same points according to y co-ordinate

#include <bits/stdc++.h>
using namespace std;
struct point
{
    int x,y;
};


int main()
{
    struct point a[100],tmp;
    int i,j,n;
    cin>>n;
    for(i=1;i<=n;i++)
    {
        cin>>a[i].x>>a[i].y;
    }
    //sort according to x co-ordinate
    for(i=1;i<=n;i++)
    {
        for(j=i+1;j<=n;j++)
        {
            if(a[i].x>a[j].x)
            {
                tmp=a[i];
                a[i]=a[j];
                a[j]=tmp;
            }
        }
    }
    //sort according to y when x points are same 
    for(i=1;i<=n;i++)
    {
        for(j=i+1;j<=n;j++)
        {
            if(a[i].x==a[j].x)
            {
            if(a[i].y>a[j].y)
            {
                tmp=a[i];
                a[i]=a[j];
                a[j]=tmp;
            }
            }
        }
    }

    for(i=1;i<=n;i++)
    {
       cout<<a[i].x<<" "<<a[i].y<<endl;

    }
    return 0;

}

Upvotes: 0

BLUEPIXY
BLUEPIXY

Reputation: 40145

You can sort indirectly by sorting the index relationship of the two sequences from index.

The following example

#include <stdio.h>
#include <stdlib.h>

int *X;

int cmp(const void *a, const void *b){
    int xi = *(int *)a;
    int xj = *(int *)b;
    return (X[xi] < X[xj]) ? -1 : (X[xi] > X[xj]);
}

int main(){
    int x[] = { 1, 4, 2, 5, 3, 7, 10 };
    int y[] = { 5, 2, 4, 3, 8, 9, 99 };
    size_t size = sizeof(x)/sizeof(*x);
    int index[size];
    int i;
    for(i = 0; i < size ; ++i){
        index[i]=i;
    }
    X = x;
    qsort(index, size, sizeof(int), cmp);
    for(i=0;i<size;++i){
        printf("(%d, %d)\n", x[index[i]], y[index[i]]);
    }
    return 0;
}

Upvotes: 1

Linear
Linear

Reputation: 22206

There are a couple easy ways to do this:

  1. Use a struct for the point

    struct point { int x, y; }

    In this case, you can have an array struct point points[NUM_POINTS], and anywhere in your sorting algorithm where you say if a[n] < a[m] instead say if a[n].x < a[m].x

  2. Since you're going to have to amend your sorting algorithm anyway, if you don't want to use a struct (which is honestly the way I'd recommend). You can alter your sorting algorithm such that it takes two arrays, and everywhere you do the operation swap(xArray,n,m), you can add swap(yArray,n,m). Depending on the algorithm you use, this can become a major hassle.

  3. The generalized version of 2 is to have two arrays: the sortable one and one of the exact same size as the sortable array that's numbered in order from 0 to ArrayLen-1. As in 2, whenever you swap(m,n) on the sortable array, also swap(m,n) on the index array. After this is done, take every other array you need sorted in the same way and put every element in sideArray[i] in the index listed in indexArray[i] (requires copying to a new array usually).

Overall, putting the data in a struct is usually the best and by far the easiest, especially for your purposes, though in some cases 3 is necessary (but usually only if you're working in some library with tight input constraints).

Upvotes: 2

Dan Kruchinin
Dan Kruchinin

Reputation: 3055

Why don't you create a new array (which could replace x and y arrays if possible) of structures where each structure stores both x and y? Something like

struct point {
    int x, y;
};

struct point points[N];

Upvotes: 3

Related Questions