PDA

View Full Version : Help with sorting QVector< QVector<int> >



m3rlin
9th January 2013, 14:47
Hi,

I have a QVector of QVectors (that is QVector< QVector <int> >. I am trying to write a basic sort algorithm for sorting the collection.
I can't seem to get the while loop right, and I am staring myself blind on it -- so I was wondering if I can get some help.

The outer Vector contains values 0 - 46 and the inner Vector contains positive numbers from 0 to 99.
My goal is to swap rows so that the highest values in the inner Vector come first, but in such a way that the corresponding values (rows) of the outer Vector move along with the swap...
Example: if vec[0][1] < vec[1][1] then swap the values in vec[0][0] and vec[0][1] with values vec[1][0] and vec[1][1] respectively.

Here is my code:
// I am receiving a QVector< QVector< int > > via a function. It is called vecToSort.

QVector< int > vecSwapLow;
QVector< int > vecSwapHigh;

for ( int x = 1; x < vecToSort.size(); x++ ) // row-by-row of outer Vector
{
int iMove = x;
int iHigh0 = vectToSort[ 1 ][ 0 ];
int iHigh1 = vectToSort[ 1 ][ 1 ];
int iLow0 = vectToSort[ 0 ][ 0 ];
int iLow1 = vectToSort[ 0 ][ 1 ];
vecSwapLow.clear()
vecSwapLow << iLow0 << iLow1;

while ( ( iMove > 0 ) && ( vecToSort[ iMove -1 ][ 1 ] > vecToSort[ x ][ 1 ] ) )
{
vecSwapHigh << iHigh0 << iHigh1;
vecToSort.replace( ( iMove - 1 ), vecSwapHigh );
iMove--;
}
vecSwapHigh.clear();
vecToSort.replace( iMove, vecSwapLow );

// after the repetition loop this codes puts the value that was replaced back into the outer Vector
// problem is that if the repetition loop is not executed, it still replaces the row, so I end up with 3 or 4 sorted values and the rest until row 46 is all the same...
}

Santosh Reddy
10th January 2013, 09:20
Check if this is what you want?



#include <QDebug>
#include <QVector>

int main(int argc, char *argv[])
{
const int inSize = 10;
const int outSize = 10;
QVector<QVector<int> > vecToSort;

// Create Vectors
for(int i = 0; i < outSize; i++)
{
QVector<int> vect;
for(int i = 0; i < inSize; i++)
vect.append(qrand());
vecToSort.append(vect);
}

qDebug() << "Before:";
for(int i = 0; i < vecToSort.size(); i++)
qDebug() << vecToSort.at(i);

// Sort Vectors
for(int i = 0; i < vecToSort.size(); i++)
for(int j = i; j < vecToSort.size(); j++)
if(vecToSort.at(i).at(0) < vecToSort.at(j).at(0))
{
QVector<int> tmp = vecToSort.at(i);
vecToSort[i] = vecToSort.at(j);
vecToSort[j] = tmp;
}

qDebug() << "After:";
for(int i = 0; i < vecToSort.size(); i++)
qDebug() << vecToSort.at(i);

return 0;
}

//Output
Before:
QVector(41, 18467, 6334, 26500, 19169, 15724, 11478, 29358, 26962, 24464)
QVector(5705, 28145, 23281, 16827, 9961, 491, 2995, 11942, 4827, 5436)
QVector(32391, 14604, 3902, 153, 292, 12382, 17421, 18716, 19718, 19895)
QVector(5447, 21726, 14771, 11538, 1869, 19912, 25667, 26299, 17035, 9894)
QVector(28703, 23811, 31322, 30333, 17673, 4664, 15141, 7711, 28253, 6868)
QVector(25547, 27644, 32662, 32757, 20037, 12859, 8723, 9741, 27529, 778)
QVector(12316, 3035, 22190, 1842, 288, 30106, 9040, 8942, 19264, 22648)
QVector(27446, 23805, 15890, 6729, 24370, 15350, 15006, 31101, 24393, 3548)
QVector(19629, 12623, 24084, 19954, 18756, 11840, 4966, 7376, 13931, 26308)
QVector(16944, 32439, 24626, 11323, 5537, 21538, 16118, 2082, 22929, 16541)
After:
QVector(32391, 14604, 3902, 153, 292, 12382, 17421, 18716, 19718, 19895)
QVector(28703, 23811, 31322, 30333, 17673, 4664, 15141, 7711, 28253, 6868)
QVector(27446, 23805, 15890, 6729, 24370, 15350, 15006, 31101, 24393, 3548)
QVector(25547, 27644, 32662, 32757, 20037, 12859, 8723, 9741, 27529, 778)
QVector(19629, 12623, 24084, 19954, 18756, 11840, 4966, 7376, 13931, 26308)
QVector(16944, 32439, 24626, 11323, 5537, 21538, 16118, 2082, 22929, 16541)
QVector(12316, 3035, 22190, 1842, 288, 30106, 9040, 8942, 19264, 22648)
QVector(5705, 28145, 23281, 16827, 9961, 491, 2995, 11942, 4827, 5436)
QVector(5447, 21726, 14771, 11538, 1869, 19912, 25667, 26299, 17035, 9894)
QVector(41, 18467, 6334, 26500, 19169, 15724, 11478, 29358, 26962, 24464)

m3rlin
10th January 2013, 13:57
Hey Santosh Reddy,

Simplicity and efficiency. Thanks. Yes indeed that was what I was looking for (except that I changed ...at(0) into at(1).
I had read the QVector class reference, but it didn't occur to me to use the index.at for a whole row. Actually I thought it wouldn't work like that so I tried the traditional approach with a while loop, but now it makes perfectly sense.

Thank you.

Santosh Reddy
10th January 2013, 14:28
Simplicity and efficiency.
It looks simple, but it is not efficient way, copying the whole vector is costly operation (copy to temp and them copy it back). Instead a pointer based approach will be more efficient like this. (Note the changes are marked)



#include <QDebug>
#include <QVector>

int main(int argc, char *argv[])
{
const int inSize = 10;
const int outSize = 10;
QVector<QVector<int> *> vecToSort; //<<<<

// Create Vectors
for(int i = 0; i < outSize; i++)
{
QVector<int> *vect = new QVector<int>(); //<<<<
for(int i = 0; i < inSize; i++)
vect->append(qrand()); //<<<<
vecToSort.append(vect);
}

qDebug() << "Before:";
for(int i = 0; i < vecToSort.size(); i++)
qDebug() << *vecToSort.at(i); //<<<<

// Sort Vectors
for(int i = 0; i < vecToSort.size(); i++)
for(int j = i; j < vecToSort.size(); j++)
if(vecToSort.at(i)->at(0) < vecToSort.at(j)->at(0)) //<<<<
{
QVector<int> *tmp = vecToSort.at(i); //<<<<
vecToSort[i] = vecToSort.at(j);
vecToSort[j] = tmp;
}

qDebug() << "After:";
for(int i = 0; i < vecToSort.size(); i++)
qDebug() << *vecToSort.at(i); //<<<<

return 0;
}