Bad Sorting a vector objects C++

Question

I have a strange problem when I try to sort vector of custom object. I have this code:

class Chromosome {
public:
   Chromosome(int c_w);       
   void setFitness(double fit);
   double getFitness() const;                
};

and compare function:

bool compareChromosomes(const Chromosome* l, const Chromosome* r) {
   return l->getFitness() <= r->getFitness();
}

I create the vector of chromosome: vector<Chromosome*> popv; and I add some chromosomes.

when I try to sort the vector with sort(popv.begin(), popv.end(), compareChromosomes);

this is the result:

BEFORE SORT:

cromosoma 0: 0.205595

cromosoma 1: 0.370121

cromosoma 2: 0.363655

cromosoma 3: 0.363655

cromosoma 4: 0.858721

cromosoma 5: 0.192359

cromosoma 6: 0.582279

cromosoma 7: 0.202899

cromosoma 8: 0.205105

cromosoma 9: 0.187058

AFTER SORT

cromosoma 0: -0.474942

cromosoma 1: 0.187058

cromosoma 2: 0.192359

cromosoma 3: 0.202899

cromosoma 4: 0.205105

cromosoma 5: 0.205595

cromosoma 6: 0.363655

cromosoma 7: 0.363655

cromosoma 8: 0.370121

cromosoma 9: 0.582279

where is the problem?

Try setting a memory breakpoint. Otherwise, the code isn't enough to tell. — Luchian Grigore
– Luchian Grigore, Commented Nov 27, 2012 at 18:54

Luchian Grigore · Accepted Answer · 2012-11-27 17:58:05Z

4

Your compare function is not strict - for two equal chromosomes, it returns true for compareChromosomes (regardless of order). Replace your condition with strict less:

bool compareChromosomes(const Chromosome* l, const Chromosome* r) {
   return l->getFitness() < r->getFitness();
   //                     |
   //                  <, not <=
}

answered Nov 27, 2012 at 17:58

Luchian Grigore

260k68 gold badges465 silver badges634 bronze badges

Sign up to request clarification or add additional context in comments.

6 Comments

Mark Ransom Over a year ago

You're right of course, but can this problem really explain the symptoms in the question?

Luchian Grigore Over a year ago

@MarkRansom of course, if equality is checked as compare(x,y) && compare(y,x).

Mark Ransom Over a year ago

I can see how that would produce an incorrect order, but how does it corrupt an element?

Luchian Grigore Over a year ago

@MarkRansom oh dear :)). I thought the problem was incorrect ordering, I didn't see an element got changed. Hmmmm... can't really tell from the code.

Blastfurnace Over a year ago

I'm only guessing but since the corrupted value is the greatest in the input dataset the incorrect compare function may cause the implementation to walk off the end of the container and cause the corruption.

|

MadCrazy · Accepted Answer · 2012-11-29 10:58:01Z

The reason why 0.858721 is changed to -0.474942 is not because of your comparison function. There must be some other reason on the code you had not posted. Try the code below: the output is ok.

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

using namespace std;

class Chromosome {
public:
  Chromosome(int c_w) :mCw(c_w) { }
  void setFitness(double fit) { mFit = fit; }
  double getFitness() const { return mFit; }
  int getCW() const { return mCw; }
private:
  int mCw;
  double mFit;
};

bool compareChromosomes(const Chromosome* l, const Chromosome* r) {
   return l->getFitness() <= r->getFitness();
}

int main( int argc, char *argv[] ) {
  // init your data
  vector<Chromosome *> popv;
  popv.push_back( new Chromosome( 0 ) );
  popv[ popv.size() - 1 ]->setFitness( 0.205595 );
  popv.push_back( new Chromosome( 1 ) );
  popv[ popv.size() - 1 ]->setFitness( 0.370121 );
  popv.push_back( new Chromosome( 2 ) );
  popv[ popv.size() - 1 ]->setFitness( 0.363655 );
  popv.push_back( new Chromosome( 3 ) );
  popv[ popv.size() - 1 ]->setFitness( 0.363655 );
  popv.push_back( new Chromosome( 4 ) );
  popv[ popv.size() - 1 ]->setFitness( 0.858721 );
  popv.push_back( new Chromosome( 5 ) );
  popv[ popv.size() - 1 ]->setFitness( 0.192359 );
  popv.push_back( new Chromosome( 6 ) );
  popv[ popv.size() - 1 ]->setFitness( 0.582279 );
  popv.push_back( new Chromosome( 7 ) );
  popv[ popv.size() - 1 ]->setFitness( 0.202899 );
  popv.push_back( new Chromosome( 8 ) );
  popv[ popv.size() - 1 ]->setFitness( 0.205105 );
  popv.push_back( new Chromosome( 9 ) );
  popv[ popv.size() - 1 ]->setFitness( 0.187058 );
  // sort
  sort( popv.begin(), popv.end(), compareChromosomes );
  for( size_t i = 0; i < popv.size(); i++ ) {
    cout << "cromosoma " << popv[i]->getCW() << ":" << popv[i]->getFitness() << endl;
  }

  return 0;
}

Collectives™ on Stack Overflow

Bad Sorting a vector objects C++

2 Answers 2

6 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

6 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related