Sorting two vectors at once?

Question

My current project involves sorting points based on their distance from the origin of an x-y coordinate plane. It has to find each point's distance from the origin, sort the distances, and outputs the points that created the distances, NOT the distance. It has to use bucketsort and vectors only. My sort is working fine, but I'm having difficulty figuring out how to make sure the distance vector and the point vector staying aligned. (The distance a B[0] was created from the point at c[0], even if the point was not initially at C[0].) Here is my code so far.

The standard user input, as an example:

0.2 0.38
0.6516 -0.1
-0.3 0.41
-0.38 0.2

First, in main, get the input from the user. The each half of the point is initially taken as its own double into vector A, then combined with its other half as a pair in vector C.

int main(){
double number; int t = 0; pair<double,double> x;
while (cin >> number){ 
    A.push_back(number);    }
while (t < A.size()){
    x = make_pair(A[t], A[t+1]); C.push_back(x); t += 2; }
int q = 0; 
while (q < (C.size() - 1)){
    findDistance(C[q].first, C[q].second);
    q++;
}

Then, all distances are found using a distance function, where the results are stored in vector B. Here is the function.

void findDistance(double x = 0, double y = 0) {
double x2 = pow(x, 2);
double y2 = pow(y, 2);
double z = x2 + y2;
double final = sqrt(z);
B.push_back(final);
}

A bucketsort organizes all of the distances, storing the results in B still.

void bucketSort(vector<double> &arr)
{
int n = B.size();
vector<double> b[n];

for (int i=0; i<n; i++)
{
   int bi = n*arr[i];
   b[bi].push_back(arr[i]);
}

for (int i=0; i<n; i++)
   sort(b[i].begin(), b[i].end());

int index = 0;
for (int i = 0; i < n; i++){
    for (int j = 0; j < b[i].size(); j++){
        arr[index++] = b[i][j]; }
    }
}

And here is where the problem is. B is sorted, but C remains in its original order. It's too costly to look through and compare values between tables to find the correct order. (One of the parameters is keeping the running time as O(n). Is there any ideas on how I can fix this?

Here is my complete code:

vector<double> A;
vector<double> B;
vector<pair<double,double>> C;

void findDistance(double x = 0, double y = 0) {
double x2 = pow(x, 2);
double y2 = pow(y, 2);
double z = x2 + y2;
double final = sqrt(z);
B.push_back(final);
}

void bucketSort(vector<double> &arr)
{
int n = B.size();
vector<double> b[n];

for (int i=0; i<n; i++)
{
   int bi = n*arr[i];
   b[bi].push_back(arr[i]);
}

for (int i=0; i<n; i++)
   sort(b[i].begin(), b[i].end());

int index = 0;
for (int i = 0; i < n; i++){
    for (int j = 0; j < b[i].size(); j++){
        arr[index++] = b[i][j]; }
    }
}

int main(){
double number; int t = 0; pair<double,double> x;
while (cin >> number){ 
    A.push_back(number);    }
while (t < A.size()){
    x = make_pair(A[t], A[t+1]); C.push_back(x); t += 2; }
cout << setprecision(5); cout << fixed; 
int q = 0; double r = 0; double d = 0; 
while (q < (C.size() - 1)){
    findDistance(C[q].first, C[q].second);
    q++;
}
bucketSort(B);
cout << showpos; cout << fixed;
//more cout here to show results
}

Here is an example input and output: input:

0.2 0.38
0.6516 -0.1
-0.3 0.41
-0.38 0.2

output:

-0.380000 +0.200000
+0.200000 +0.380000
-0.300000 +0.410000
+0.651600 -0.100000

Any help would be appreciated, please and thank you.

Since computing a distance is a constant-time operation, you might as well omit the distance vector, and only sort the point vector based on distances. — Giulio Franco, Mar 05 '15 at 09:34
If you want to sort them together, use a struct which encapsulates both the point and the distance. — Giulio Franco, Mar 05 '15 at 09:35
Related to [sorting-zipped-locked-containers-in-c-using-boost-or-the-stl](http://stackoverflow.com/questions/13840998/sorting-zipped-locked-containers-in-c-using-boost-or-the-stl) — Jarod42, Mar 05 '15 at 09:41

Andrey Derevyanko · Answer 1 · 2015-03-05T12:41:08.210

First I think you should decide if you really need to know the distances or you need them just to sort the points vector. If you don't need them there is no need to store them separately. What I'd do is:

Create a class of Point (that has x and y as members).
Define compare operator for it (to be able to sort).
Get points from user input (almost same way you do now).
Call standard sort algorithm.

Also it may be useful to implement a member function like double get_distance(). Also if you plan to get it several times member double distance can be useful.

As an alternative you can define comparison function for pair<double,double> elements and use it as Compare function during sort.

Hope it makes sense what I wrote.

score 0 · Answer 2 · answered Mar 06 '15 at 09:22

A common trick in such cases is to first sort a helper vector, which contains the indices of the vectors that you really want to sort. That is to say, you sort vector<size_t> H not by i<j but by B[i] < B[j].

Afterwards, you create Bnew[i] = B[H[i]] and Cnew[i] = C[H[i]].

Sorting two vectors at once?

2 Answers2