CODEWITHSUNDEEP
c++sortingstd-pair
Pablo Acuña
Pablo Acuña

Reputation: 77

sort operator not working in C++

I'm having trouble using my sort operator since I need to sort only the first element in the pair. The code is simple but is not working:

The operator is defined in:

struct sort_pred {
    bool operator()(const CromosomaIndex &left, const CromosomaIndex &right) { 
        return left.first < right.first;
    }
};

and the type is

typedef std::pair<double,int> CromosomaIndex;

I'm trying to sort the array like this:

CromosomaIndex nuevo[2];
nuevo[0].first = 0.01;
nuevo[0].second = 0;
nuevo[1].first = 0.009;
nuevo[1].second = 1;
int elements = sizeof(nuevo) / sizeof(nuevo[0]);
sort(nuevo, nuevo+ elements, sort_pred());

But the problem is that this is sorting the first and the second element and I only want to sort the first element and keep the second fixed. Any thoughts?

Upvotes: 2

Views: 431

Answers (3)

David Rodr&#237;guez - dribeas
David Rodr&#237;guez - dribeas

Reputation: 208323

I am not sure that you understood the answer to the other question, but you do want the whole pair to be reordered according to the double value. The original index (the int) must be attached to the double that was in that location in the original vector so that you can recover the location. Note that if you sorted only the double within the pair, then the value of the int would be the location in the array... which does not need to be maintained as a datum at all.

Alternatively, you can consider a similar (although slightly different) solution. Create a single vector of integers that is initialized with values in the range [0..N) where N is the size of the vector of doubles. Then sort the vector of indices using a comparator functor that instead of looking at the value (int) passed in will check the value in the original double vector:

struct dereference_cmp {
   std::vector<double> const & d_data;
   dereference_cmp( std::vector<double> const & data ) : d_data(data) {}
   bool operator()( int lhs, int rhs ) const {
      return d_data[lhs] < d_data[rhs];
   }
};
std::vector<double> d = ...;
std::vector<int> ints;
ints.reserve( d.size() );
for ( int i = 0; i < d.size(); ++i ) ints.push_back(i);
std::sort( d.begin(), d.end(), dereference_cmp(d) );

In this approach, note that what is not being reordered are the doubles, but rather the vector of indices. After the sort completes the vector of indices will contain locations into the vector of double such that i < j => d[ ints[i] ] <= d[ ints[j] ].

Note that in the whole process, what you want to reorder is the indices (in the original approach to be able to reconstruct the unsorted vector, in this approach to be able to find the values in sorted order), and the original vector is there only to provide the criterion for the sort.

Also note that the only reason to sort only the indices and not a modified container with both the value and the index would be if the cost of moving the data was high (say that each datum is a large object that cannot be cheaply moved, as a struct holding an array --not vector-- of data).

Upvotes: 1

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 726489

This approach sorts pairs as a single unit, which is what it is expected to do: it never make sense to break up the first and the second of the pair. If you would like to sort only the first item and leave the second in place, you will end up with a different set of pairs.

If you want to sort the first separately from the second, place them in separate arrays (better yet, use vectors) and sort the first vector. Then iterate both vectors, and make a new set of pairs.

Upvotes: 2

Ben Voigt
Ben Voigt

Reputation: 283614

If you want the results to depend on the original order, use std::stable_sort.

Upvotes: 5

Related Questions