replace method with weird behavior. Don't know how to fix it.

[robgeek]

Hi!

I have a QVector of Number object which I have to sort by descending, but look at the output:


QVector<Number> Game::descendingOrderVector(QVector<Number> ranking) {
int length = ranking.size( );
length--;

cout << "BEFORE" << endl;
for(int i = 0; i < ranking.size( ); i++)
cout << "(" << ranking[i].val << ", " << ranking[i].acum << ") ";

for(int i = 0; i < length; i++)
for(int j = 0; j < length; j++)
if(ranking[ j ].acum < ranking[j + 1].acum)
ranking.replace(j, ranking.at(j + 1));

cout << endl << "AFTER" << endl;
for(int i = 0; i < ranking.size( ); i++)
cout << "(" << ranking[i].val << ", " << ranking[i].acum << ") ";

return ranking;
}


BEFORE
(2, 87) (4, 33) (1, 162) (5, 22) (6, 21) (3, 61) (7, 14) (9, 3) (10, 3) (11, 4) (8, 4) (13, 2) (20, 1)

AFTER
(1, 162) (2, 87) (3, 61) (4, 33) (5, 22) (6, 21) (7, 14) (8, 4) (11, 4) (11, 4) (11, 4) (13, 2) (20, 1)


I believe the problem is with replace() because if i use the following code my method sorts correctly.

Number aux;

if(ranking[ j ].acum < ranking[j + 1].acum) {
aux.val = ranking[ j ].val;
aux.acum = ranking[ j ].acum;

ranking[ j ].val = ranking[j + 1].val;
ranking[ j ].acum = ranking[j + 1].acum;

ranking[j + 1].val = aux.val;
ranking[j + 1].acum = aux.acum;
}

[ars]

Hello,

you are right in your assumption that the misbehavior is related to replace() method. To be more precise: QVector::replace(i, val) replaces the vector content at index i with the value val. But for sorting you do not want to replace the value at postion i with the value at position i+1. Instead, you need to swap the two positions. And that's exactly what your second code snippet does. So it is not a problem of replace method. The problem is related to using replace where you should use swap!

But why are you implementing sorting yourself using an algorithm with quadratic runtime? Better use std::sort() (see http://www.cplusplus.com/reference/algorithm/sort/). For your case, use the second form and provide a compare function.

Best regards
ars

[robgeek]

Thanks for your answer but I cannot use swap method with QVectors.

/home/rob/Programming/C-C++/Linux/Qt/Game/game.cpp:180: error: no matching function for call to 'QVector<Number>::swap(int&, int)'
ranking.swap(j, (j + 1));
^

I'll read about std::sort().

[ars]

Hello,

of course you cannot use the QVector::swap() method as it swaps the contents of two vectors. You could use std::swap() instead, if you want to keep your sorting algorithm. In this case, replace your
ranking.replace(j, ranking.at(j + 1)); by

std::swap(ranking[j],ranking[j+1]);.
See http://www.cplusplus.com/reference/utility/swap/?kw=swap.

Anyway it is better to use std::sort instead of the quick fix of your algorithm using std::swap.
Best regards
ars

Added after 40 minutes:

Here's a quick implementation using std::vector (Simply replace my data structures with yours):


#include <vector>
#include <algorithm> // std::sort()

#include <string>
#include <iostream>

struct Number
{
int val;
int acum;
};

bool descCompare(const Number& a, const Number& b)
{
// returns a before b
return (a.acum > b.acum);
}

std::vector<Number> sortDescending1(const std::vector<Number>& ranking)
{
std::vector<Number> result(ranking);
std::sort(result.begin(), result.end(), descCompare);
return result;
}

std::vector<Number> sortDescending2(const std::vector<Number>& ranking)
{
std::vector<Number> result(ranking);
std::sort(result.begin(), result.end(), [](const Number& a, const Number& b){return (a.acum > b.acum);});
return result;
}

Some explanation:
sortDescending1() sorts the vector using the global boolean compare function descCompare(a,b) where a,b are of type Number. This function returns true if a should go before b. In your case, a.acum has to be greater than b.acum. This sort function works with the standard compiler settings.

sortDescending2() uses a lambda expression for comparison. This function compiles only if you have configured your project for C++11. The lambda expression does excatly the same as the global comparison function. However, you need not define an explicit comparison function. You just define the comparison function at the place you need it.

Best regards
ars

[robgeek]

Thank you very much sir!