CODEWITHSUNDEEP
c++sortingvectorstruct
user2373581
user2373581

Reputation: 69

sorting higher and lower values in a vector

I got a vector that contains 4 elements who are not sorted, the vector looks like this :

vector<positionInfo> objects

where positionInfo is a struct :

struct positionInfo
{
  int X_pos;
  int Y_pos;
}

now, these 4 elements are not sorted, but I want them to be in a specific order, which is :

this is just to easily access any of the 4 points who form a cube, using a lot of variables can probably get me what I want but that's not really optimal I think, are there any algorithms I can use to decrease the size of the code and increase the speed?

Upvotes: 1

Views: 271

Answers (3)

Boris
Boris

Reputation: 622

If you completely sure that you have a solution, you can partly use std::sort.

For example (3 steps):

Overload < operator:

bool
operator < (const positionInfo & left, const positionInfo & right)
{
    return left.X + left.Y < right.X + right.Y;
}

Next, sort your vector:

std::sort( &objects[0], &objects[4] );

Notice, that in this example vector has precisely 4 elements.

As a result, you will get a vector, where first and last elements are sorted according to your wish.

Last step - swap interal elements if it needs:

if ( objects[1].X < objects[2].X )
    std::swap( &objects[1], &objects[2] );

Done.

Upvotes: 2

Boris Strandjev
Boris Strandjev

Reputation: 46943

Several points:

  • Four points do not form a cube - it has 8 vertices. IF you meant determine a cube probably you need 3 dimensions. I am assuming you speak of square
  • In case you actually are not dealing with squares, but with random 4 points your sorting is not clear - Element 1 ( [0] ) must have the lowest Y and X pos for example it is not required to have the lowest y and x in the same point.

If, however, you meant square, not cube and are really sure you want to deal with this situation you can do it the following way

  • Cycle all four vertices
  • find the minimal and maximal x and ys
  • because you are sure of the situation you deal with you can create the 4 points of interest out of those 4 values.

Upvotes: 0

Lol4t0
Lol4t0

Reputation: 12547

Your conditions are not local to the data. You should have an information about all the elements to calculate, if one element is bigger or smaller, than another.

I'l illustrate this with the image:

enter image description here

Considering only (1) and (2) or (3) and (4) it's impossible to say, what should be bigger:

If (1) and (2) had their y coordinates greater then (3) and (4), they would swap their positions.

Usual search algorithms, however, work only in assumption, that you can compare elements locally, so you could decide, which of two elements is greater, considering only 2 elements.

So you cannot use standard sort algorithms.

Instead, you should make new vector and fill it with elements according to the conditions:

new_objects[0] = find_elememt_with_lowet_x_and_y(objects);
new_objects[1] = find_element_with_highets_x_and_lowest_y(objects); 
//....
objects = new_objects;

Upvotes: 0

Related Questions