Sorting coordinates stored in 2d array

[BBrandon]

Hello! I've been recently working on graph problems and problems with coordinates, and I found that if I knew how to create a specific function, it would be quite useful. So I am given a list of N coordinates. I started my program by storing this in a 2d array, with the first row being x-coordinates and the second row being y-coordinates. Now this means that if I ever need the Nth coordinate, I could easily iterate to the Nth column and take both numbers.

But I want to also sort the x-coordinates so that they will be arranged by least to greatest. But in order to make sure I can still retrieve the coordinates, any x-coordinates moved would also need their respective y-coordinate moved. In other words, I want to sort the first row from least to greatest, but whenever an element needs to be moved, I want to move the entire column of the element with it. Additionally, all coordinates are non-negative integers, and all integers in the same row are guaranteed to be unique. Does anyone have any ideas how to do this in an efficient way? And would that method work in the same scenario, but with sorting the y-coordinate instead? I can also give a few examples as well.

EXAMPLE #1:
{2, 3, 4, 5, 1} -> {1, 2, 3, 4, 5}
{1, 2, 3, 4, 5} -> {5, 1, 2, 3, 4}

(Note that the only x-coordinate that needed to be sorted was the 1 in the last position, and it needed to be placed in the first position of the row. But I also want the program to take the 5 in the same position below the 1 and take it to the same new position.)

EXAMPLE #2:
{2, 0, 3, 5} -> {0, 2, 3, 5}
{0, 1, 2, 3} -> {1, 0, 2, 3}

[lastchance]

Put your (x,y) coordinates in a single struct, say:

struct Point2d
{
   double x;
   double y;
};

Then use stable sort:
http://www.cplusplus.com/reference/algorithm/stable_sort/
with a comparator based on the x coordinate only.

[oggin]

Using the point2d structure, and a simple bubblesort.

#include<vector>
#include<iostream>
using namespace std;

struct point2d
{
   double x;
   double y;
};

enum {dotx=0,doty=1};

void bubblesort(vector<point2d> &p,int field)
{
	for (int i=0;i<p.size()-1;i++)
	{
		for(int j=i+1;j<p.size();j++)
		{
		if(field==dotx)	if(p[i].x>p[j].x) swap (p[i],p[j]);
		if(field==doty)	if(p[i].y>p[j].y) swap (p[i],p[j]);
		}
	}		
}



void print(vector<point2d> v)
{
	cout<<"x"<<"   "<<"y"<<endl;
	for(int i=0;i<v.size();i++)
	{
		cout<<v[i].x<<"   "<<v[i].y<<endl;
	}
	cout<<endl;
}


int main()
{
	vector<point2d> v={{2,1},
	                   {3,2},
	                   {4,3},
	                   {5,4},
	                   {1,5}};
print(v);                   
bubblesort(v,dotx);
print(v);
bubblesort(v,doty);
print(v);

system("pause");	                   
	                   
}  

Bubblesort is slow for large data arrays (vectors)

[lastchance]

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Point2d
{
   double x, y;
};


void write( const vector<Point2d> &V )
{
   for ( Point2d pt : V ) cout << pt.x << ' ' << pt.y << '\n';
}


template <typename T> void sort( vector<T> &V, double T::*ptr )
{
   stable_sort( V.begin(), V.end(), [ ptr ]( T a, T b ){ return a.*ptr < b.*ptr; } );
}


int main()
{
   vector<Point2d> V = { { 2, 1 }, { 3, 2 }, { 4, 3 }, { 5, 4 }, { 1, 5 } };
   cout << "Initial:\n";   write( V );

   sort( V, &Point2d::x );
   cout << "\nSorted on x:\n";   write( V );

   sort( V, &Point2d::y );
   cout << "\nSorted on y:\n";   write( V );
}

Initial:
2 1
3 2
4 3
5 4
1 5

Sorted on x:
1 5
2 1
3 2
4 3
5 4

Sorted on y:
2 1
3 2
4 3
5 4
1 5

[JLBorges]

> Now this means that if I ever need the Nth coordinate,
> I could easily iterate to the Nth column and take both numbers.

So, don't change values of the items in the original array; keep it immutable


> But I want to also sort the x-coordinates so that they will be arranged by least to greatest.
> but whenever an element needs to be moved, I want to move the entire column of the element with it.

Do a tag sort on the column indices, and access the columns in the order of the tags.
This will extend seamlessly to any number of columns.

For example:

#include <iostream>
#include <algorithm>



int main()
{
    const int coords[2][5] = { { 2, 3, 4, 5, 1 }, { 1, 2, 3, 4, 5 } } ; // note: const; this never changes
    const int X = 0 ; // x coordinates are on row 0
    const int Y = 1 ; // y coordinates are on row 1

    int tags[5] { 0, 1, 2, 3, 4 } ; // positions (cols) in the 2d array (these tags can be sorted)

    const auto print_on_tags = [&] // print in the order of tags
    {
        for( int pos : tags ) std::cout << '(' << coords[X][pos] << ',' << coords[Y][pos] << ") " ;
        std::cout << '\n' ;
    };

    // indirect sort: sort tags on a particular row of interest (compare items in that row)
    const auto sort_tags_on = [&] ( int row )
    {
        std::sort( std::begin(tags), std::end(tags),
                   [&]( int a, int b ) { return coords[row][a] < coords[row][b] ; } ) ;
    };

    sort_tags_on(X) ; // indirect sort on X (sort tags on the X coordinate)
    std::cout << "sorted on X: " ;
    print_on_tags() ; // print coordinates in sorted order of tags

    sort_tags_on(Y) ; // indirect sort on Y (sort tags on the Y coordinate)
    std::cout << "sorted on Y: " ;
    print_on_tags() ; // print coordinates in sorted order of tags
}

http://coliru.stacked-crooked.com/a/a6aa4b883da78e16