2

I have many points (a,b) and I stored x coordinate in a[] and y coordinate in b[]. Now I need to sort these points wrt x-coordinate or y-coordinate. I know that there is concept of pairs in C++ but is there any better way of doing this. Please give answers in C/C++.

Mani Sankar
  • 800
  • 1
  • 9
  • 19
  • 2
    I can't imagine a better way of storing pairs of two integers then in a struct of pair of two integers. –  Jan 13 '15 at 05:12
  • Are you asking about C or C++, or do you want something that works in both? – user253751 Jan 13 '15 at 06:05
  • You can create a custom iterator for `a` such that when you `sort` it, it also modifies the order in `b` to remain consistent. – Marc Glisse Jan 13 '15 at 07:09

5 Answers5

6

You can store the pair of coordinates using std::pair<int, int>, or as the answer by @Gopi indicates by a struct.

A collection of either of those can be sorted by the X coordinate or by the Y coordinate by using a lambda function, a functor, or a global function.

// A vector of vertices.
std::vector<std::pair<int, int>> vertices;

// Sort the vertices by X coordinates using a lambda function to order them
std::sort(vertices.begin(), vertices.end(),
         [](auto const& a, auto const& b) { return a.first < b.first; });

// Sort the vertices by Y coordinates using a lambda function to order them
std::sort(vertices.begin(), vertices.end(),
          [](auto const& a, auto const& b) { return a.second < b.second; });
R Sahu
  • 204,454
  • 14
  • 159
  • 270
  • `pair` already has a comparison function, it compares `first` and if they are equal it compares `second` so you don't need to pass a lambda to the first sort there. – Jonathan Mee Jan 13 '15 at 16:26
  • @JonathanMee, true. If a user wants to sort them by just the X coordinate and ignore the Y coordinate, then the compare function is necessary. – R Sahu Jan 13 '15 at 16:51
5
struct vertex
{
int x;
int y;
};

Then sort the structures accordingly.

Gopi
  • 19,784
  • 4
  • 24
  • 36
  • Can you please elaborate on how to sort the array of these structures using sort() function of C++ – Mani Sankar Jan 13 '15 at 05:17
  • 2
    @user3901994 `std::sort(std::begin(an_array), std::end(an_array), [] (vertex const & a, vertex const & b) { return a.x < b.x; });` <-- replace `a.x < b.x` with `a.y < b.y` to sort by the `y` field instead of the `x` field. – cdhowie Jan 13 '15 at 05:22
  • 2
    @cdhowie I think it is instrumental to point out that your compartor utilizes lambda functions and needs the C++11 flag to compile. – Mustafa Jan 13 '15 at 05:24
2

You can use a struct as pointed out and shown in other answers. However, if you define your own struct you will need to define a comparator function to use with the sorting algorithm or overload the < operator.

The advantage of using std::pair is that you won't need to define a comparator because std::pair overloads the operator < to sort by first element first then second element. See this answer for an example.

Community
  • 1
  • 1
Mustafa
  • 1,814
  • 3
  • 17
  • 25
  • *"`std::pair is that you won't need to define a comparator"* - that's certainly worthy of mention but only works for increasing order of `.first`... – Tony Delroy Jan 13 '15 at 05:32
0

The best way is struct as the answer by @Gopi. For lexicographical sorting you can use std::tie (http://en.cppreference.com/w/cpp/utility/tuple/tie).

struct vertex
{
    int x;
    int y;
    bool less_x(const struct vertex& b) const { return std::tie(x,y) < std::tie(b.x, b.y); }
    bool less_y(const struct vertex& b) const { return std::tie(y,x) < std::tie(b.y, b.x); }
};
Konstantin Myachin
  • 11
  • 1
0
int c = x*n + y    where, n>x and n>y 

x=c/n 
y=c%n

When you need x simply c/n will give x and for y use c%n gives y.

Note: Works for positive coordinates only

krishankantray
  • 73
  • 1
  • 2
  • 8