sort operator not working in C++

Question

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?

I gave you a solution to keep them in the same order in which `second` originally occurred. But I can't tell from your question if that's what you actually want. Are you trying to separate pairs and have them associated differently after the sort? That's really unusual, and suggests that they probably shouldn't be members of the same object to begin with. — Ben Voigt, Aug 26 '12 at 02:37
What I need is only sort an array of doubles and later be able to recuperate their original indexes. I was trying the implementation in http://stackoverflow.com/questions/1577475/c-sorting-and-keeping-track-of-indexes but is not working for me...thansk for answer — Pablo Acuña, Aug 26 '12 at 03:36
What do you mean it is not working? After sorting, `nuevo[0]` will be the pair `{0.009,1}` and `nuevo[1]` will be `{0.01,0}`. Why is that not what you want? — jogojapan, Aug 26 '12 at 06:49

score 5 · Answer 1 · answered Aug 26 '12 at 02:35

5

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

answered Aug 26 '12 at 02:35

Ben Voigt

277,958
43
419
720

score 2 · Answer 2 · answered Aug 26 '12 at 02:36

2

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.

answered Aug 26 '12 at 02:36

Sergey Kalinichenko

714,442
84
1,110
1,523

thanks for the answer, I was trying the code from http://stackoverflow.com/questions/1577475/c-sorting-and-keeping-track-of-indexes so I don't know what's different – Pablo Acuña Aug 26 '12 at 03:40
@PabloAcuña Then your sort does the right thing (see it on [ideone](http://ideone.com/RJ7ly)), it should sort both items comparing only the first one - that is the whole idea behind that answer at the link. The `first` tells you what item you see, and the second one tells you what was the item's index in the unsorted array. – Sergey Kalinichenko Aug 26 '12 at 11:09

David Rodríguez - dribeas · Accepted Answer · 2012-08-26T04:07:32.000

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).

sort operator not working in C++

3 Answers3