Member Avatar for daviddoria

I've seen that a vector can be sorted using

vector<double> V;
vector<int> Index;
V.push_back(9);
V.push_back(10);
V.push_back(8);
Index.push_back(0);
Index.push_back(1);
Index.push_back(2);
sort(V.begin(), V.end());

If I want to sort Index according to how V was sorted, there is an optional third parameter to sort() that will do this. I don't understand how to specify this third parameter. I saw an example that defined an iterator, but that was for sorting a fancier class than just doubles.

Can someone point me in the right direction?

Thanks!

David

  • 3 Contributors
  • 5 Replies
  • 2K Views
  • 2 Years Discussion Span
  • Latest Post Latest Post by daviddoria

Dani AI

Generated

If by "parallel" you mean keeping two arrays in lockstep (not parallel execution), the cleanest fix is to stop sorting V directly and instead sort an index permutation using the 3rd parameter of std::sort. That comparator can look into V while reordering Index. This answers ’s original question and complements ’s and ’s suggestions when you have more than two arrays to keep aligned.

std::vector<double> V{9, 10, 8};
std::vector<int> Index(V.size());
std::iota(Index.begin(), Index.end(), 0);

// Sort Index by comparing the referenced values in V
std::stable_sort(Index.begin(), Index.end(),
    [&](int a, int b){
        if (V[a] == V[b]) return a < b; // deterministic tie-break
        return V[a] < V[b];
    });

// V in sorted order without touching V:
for (int i : Index) std::cout << V[i] << ' ';  // 8 9 10

Now you can either:

  • Leave V alone and always access through Index (cheap and safe), or
  • Apply the same permutation to V (and any sibling arrays) in one pass:
template<class T>
void apply_order(const std::vector<int>& order, std::vector<T>& xs) {
    std::vector<T> tmp; tmp.reserve(xs.size());
    for (int i : order) tmp.push_back(std::move(xs[i]));
    xs.swap(tmp);
}

// Example:
// apply_order(Index, V);           // V becomes sorted
// apply_order(Index, SomeOther);   // stays in lockstep with V

Important: if you already sorted V, you cannot uniquely recover the original-to-sorted mapping, especially with duplicates. Next time, build Index with iota, sort Index with the comparator above, then either access V via Index or apply_order to both V and Index. Using a pair/struct, as suggested, also works; the permutation approach scales better when you have many related arrays and lets you choose stable_sort to keep equal values in original order. If you truly meant parallel execution, C++17 adds execution policies: you can pass std::execution::par to the same stable_sort call to parallelize the permutation sort.

Recommended Answers

All 5 Replies

Member Avatar for Ancient Dragon

Member Avatar for daviddoria

since V is already sorted, how would I sort Index based on how V WAS sorted??

Member Avatar for Ancient Dragon

you will have to sort them both at the same time. You might have to write your own sort algorithm because I don't think std::sort will support that.

Or change the algorithm and create a structure with an int and a double member, then have a vector of these structures and sort by the double member.

struct num
{
   inb index;
   double v;
};
vector<num> array;
Member Avatar for Frenske

This is how it solved my problem for parallel sorting two vectors. I am bit of a noob and more comfortable in Fortran hence that's why I made a function rather than a struct or class. :D I have read that C++ programmers prefer not to pass vectors but rather pass the iterator, but this seems to work for me fine, albeit I only need to sort small vectors of 2 to 3 elements.

void ParallelSort( std::vector<double> &vec1, std::vector<double> &vec2, int nlength)
{
  // create a vector of pairs
  std::vector< std::pair<double,double> > combovec;
  // fill the vector of pairs with the elements of vec 1 and vec2
  for ( int it=0; it<vec1.size(); ++it ) combovec.push_back( std::make_pair( vec1.at(it),vec2.at(it) ));
  // sort the vector this will be done on the first element of a pair
  std::sort( combovec.begin(),combovec.end() );
  // overwrite the vec1 and vec2 with the sorted elements of the paris
  for ( int it=0; it<vec1.size(); ++it )
	{
		vec1.at(it) = combovec.at(it).first;
		vec2.at(it) = combovec.at(it).second;
	}
}
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.