C++, Sort One Vector Based on Another One

C++, Sort One Vector Based On Another One

As already suggested in other answers: Combining the name and the score of each individual is likely the simplest solution.

Generically, this can be achieved with what is sometimes referred to as a "zip" operation: Combining two vectors into a vector of pairs - along with a corresponding "unzip".

Implemented generically, this may look as follows:

#include <vector>
#include <string>
#include <algorithm>
#include <iostream>
#include <iterator>

// Fill the zipped vector with pairs consisting of the
// corresponding elements of a and b. (This assumes 
// that the vectors have equal length)
template <typename A, typename B>
void zip(
    const std::vector<A> &a, 
    const std::vector<B> &b, 
    std::vector<std::pair<A,B>> &zipped)
{
    for(size_t i=0; i<a.size(); ++i)
    {
        zipped.push_back(std::make_pair(a[i], b[i]));
    }
}

// Write the first and second element of the pairs in 
// the given zipped vector into a and b. (This assumes 
// that the vectors have equal length)
template <typename A, typename B>
void unzip(
    const std::vector<std::pair<A, B>> &zipped, 
    std::vector<A> &a, 
    std::vector<B> &b)
{
    for(size_t i=0; i<a.size(); i++)
    {
        a[i] = zipped[i].first;
        b[i] = zipped[i].second;
    }
}

int main(int argc, char* argv[])
{
    std::vector<std::string> names {"Karl", "Martin", "Paul", "Jennie"};
    std::vector<int> score {45, 5, 14, 24};

    // Zip the vectors together
    std::vector<std::pair<std::string,int>> zipped;
    zip(names, score, zipped);

    // Sort the vector of pairs
    std::sort(std::begin(zipped), std::end(zipped), 
        [&](const auto& a, const auto& b)
        {
            return a.second > b.second;
        });

    // Write the sorted pairs back to the original vectors
    unzip(zipped, names, score);

    for(size_t i=0; i<names.size(); i++)
    {
        std::cout << names[i] << " : " << score[i] << std::endl;
    }
    return 0;
}

Sort one vector according to another

Indeed you can re-use the solution from the link you shared to solve your problem. But you need to keep building the index vector (and I believe there's no need to modify the time or amplitude vectors).

The index vector is used to store the index/position of the time vector values sorted from smallest to largest, so for time={5, 16, 4, 7}:

index[0] will contain the index of the smallest value from time (which is 4, at position 2), hence index[0]=2

index[1] will contain the index of the 2nd smallest value from time (which is 5, at position 0), hence index[1]=0

etc.

And since amplitude's order is based on time you can use index[pos] to access both vectors when building your tree:

time[index[pos]] and amplitude[index[pos]]

Code with the corrections:

#include <iostream>
#include <vector>
#include <algorithm>

int  main(){

    std::vector<int> time={5, 16, 4, 7};
    std::vector<int> amplitude={10,17,8,16};
    std::vector<int> index(time.size(), 0);

    for (int i = 0 ; i != index.size() ; i++) {
        index[i] = i;
    }

    sort(index.begin(), index.end(),
         [&](const int& a, const int& b) {
            return (time[a] < time[b]);
          }
    );

    std::cout << "Time \t Ampl \t idx" << std::endl;
    for (int ii = 0 ; ii != index.size() ; ++ii) {
        std::cout << time[index[ii]] << " \t " << amplitude[index[ii]] << " \t " << index[ii] << std::endl;
    }
}

Output:

Time     Ampl    idx
4        8       2
5        10      0
7        16      3
16       17      1

---

But not only does it not work, it gives me something different each time

That happened because the parameters that the lambda was receiving were from data2={10,17,8,16} and those values were being used as index to access the data vector at return (data[a] < data[b]). It caused some random sorting because it was accessing out of the vector's range and reading garbage from memory (hence the random behavior).

Sorting a vector using values in another vector

You can make a third vector of indexes and sort that indirectly. After it's sorted, you can access the original vector through the sorted indexes:

std::vector<Foo> foo_vec = /* ... */;
std::vector<int> x_vec = /* ... */;
std::vector<std::size_t> index_vec;

assert(foo_vec.size() == x_vec.size());
for (std::size_t i = 0; i != foo_vec.size(); ++i) { index_vec.push_back(i); }

std::sort(
    index_vec.begin(), index_vec.end(),
    [&](std::size_t a, std::size_t b) { return x_vec[a] < x_vec[b]; });

for (std::size_t i = 0; i != index_vec.size(); ++i)
{
    std::cout << "Sorted element " << i << " is "
              << foo_vec[index_vec[i]] << "\n";
}

Note that this operation is entirely non-invasive, since everything happens indirectly.

Sorting one vector with respect to another - most efficient way?

One common way is to create an index and sort it, rather than sorting the original values. This is known as indirect sort or argsort.

Example:

using values_t = std::vector<float>;
using index_t = std::vector<uint8_t>;

index_t make_sorted_index(values_t const& values) {
    index_t index(values.size());
    std::iota(index.begin(), index.end(), 0);
    std::sort(index.begin(), index.end(), [&values](uint8_t a, uint8_t b) { return values[a] > values[b]; } );
    return index;
}

int main() {
    values_t a = {2,4,3,1};
    values_t b = {1,2,3,4};

    auto index = make_sorted_index(a);

    std::cout << "A = {";
    for(auto i : index)
        std::cout << a[i] << ',';
    std::cout << "\b}\n";

    std::cout << "B = {";
    for(auto i : index)
        std::cout << b[i] << ',';
    std::cout << "\b}\n";
}

Outputs:

A = {4,3,2,1}
B = {2,3,1,4}

Sort one vector based on other

We can use that as index

i1 <- sort(x, index.return=TRUE)$ix

Or with order

i1 <- order(x)
x[i1]
#[1] 1 2 4 6 7 9

y[i1]
#[1] 2 9 6 5 1 8

Sorting vector based on another sorted vector

If vector2 consists of numbers that always appear in vector1, you can map numbers from vector1, for example vector1 is [3, 2, 4] and vector2 is [4, 3];

1. Map all elements to indexes for exampe 3->0, 2->1, 4->2
   (keys are numbers and values are indexes). Use map or hashmap for
   it.
2. Now loop through vector2, for each element search for it in the map and replace it with value from map: 4 becomes 2, 3 becomes 0 so now vector2 becomes [2, 0]
3. Now use sort(vector2.begin(), vector2.end()); vector2 becomes [0, 2]
4. Now loop through vector2 and for each element i replace it with vector1[i]:
   0->3 (because number at the 0th index in vector1 is 3), 2->4 (because number at the 2nd index in vector1 is 4).
   Hope this helps.

Sort one vector using another in nonincreasing order

You could zip, sort, and unzip.

#include <iostream>
#include <vector>
#include <algorithm>

//converts two vectors into vector of pairs
template <typename T, typename U>
auto zip(T t, U u) {
  std::vector<std::pair<typename T::value_type,typename U::value_type>> pairs;
  for (size_t i = 0; i < t.size(); ++i){
    pairs.emplace_back(u[i],t[i]);
  }
  return pairs;
}

//converts a vector of pairs, back into two two vectors
template <typename T, typename U, typename V>
void unzip(V pairs, T & t, U & u) {
  for (auto const& it: pairs){
    u.emplace_back(it.first);
    t.emplace_back(it.second);
  }
}

int main(){

  //vectors
  std::vector<int> v1  = {0, 5, 5, 2,  10};
  std::vector<int> v2  = {0 ,2, 6, 20, 5};

  //zip vectors
  auto pairs = zip(v1,v2);

  //sort them
  std::sort(pairs.begin(),pairs.end(),std::greater<>());

  //unzip them
  v1.clear();
  v2.clear();
  unzip(pairs,v1,v2);

  //print
  std::cout << '\n';
  for (auto i: v1) std::cout << i << ' ';
  std::cout << '\n';
  for (auto i: v2) std::cout << i << ' ';
  std::cout << '\n';

} 

---

Related Topics