having trouble with qStableSort

manny

Hello,

I was using an example out of a book called "c++ programming a gui with qt4". Basically I am having trouble understanding how qStableSort works, and how it uses the returns provided by the operator() function.

here is the qStableSort call:

    qStableSort(rows.begin, rows.end, compare);

here is the compare function that acts as the less than function provided in the qt docs about qSorted action.

    if(ascending)    //ascending is a boolean varible to see if the user has clicked ascending
            {
                return row1 < row2;
            }
            
            else   //else the user must have clicked descending
                return row1 > row2;

from what i can understand if ascending is true than we check to see if row1 is less than row2. if it is true than i guess that qStableSort won't change anything. however if it is false, row2 will switch positions with row1.

however, if the user clicks descending, then we have to test whether or not row1 > row2. if it is, it will return true. However, wouldn't returning true make qStableSort believe that row1 is less than row2 and then have the two switched because that was what happened when the user hit ascending? This is the main reason why i am confused.

thanks, any help is greatly appreciated

Chris Kawa

Lets take a step back for a moment.
Stable sort is an algorithm that sorts given range and preserves a relative order of elements that are equal.
To sort a range we need a way to tell for any given two elements which one of them is "lesser". The "greater" and "equal to" can be extracted from it using algebra if you remember your basic math: a==b can be defined as !(a<b) && !(b<a) and a>b can be defined as !(a<b) && !(a==b).

The "lesser" can mean anything our "compare" function defines. It can mean "less then" in mathematical sense for number or it can mean "has more pink", "crashes less often", or whatever you imagine. So what I'm saying is that you shouldn't be stuck on the "<" sign and what it means for numbers or strings, because the purpose of that "compare" function is exactly to define what "<" means.

In this case we want to sort either in ascending or descending order. For ascending order we want to define "a is less then b" as "a<b returns true". For descending order we define it in reverse so "a>b is true". It is a little counter-intuitive because we define "less then" to be really "greater then" in mathematical sense, but sorting doesn't care about mathematical sense, only what you provide it with.

So in the above code if we return true for "row1 > row2" (for the descending case), what we're really doing is saying: "ok, I'm defiining row1 is less then row2 to mean operator>(row1, row2) returns true".

btw. I know you're reading a Qt4 book, but I'm just gonna remind you that with Qt5 the Qt's algorithms are discouraged and you should prefer the std:: counterparts, so in this case std::stable_sort.

manny

I think i got it, maybe.

basically i ran some tests. here is the following code:

    int main(int argc, char *argv[])
    {
        QList<QString> str = {"a", "b", "c", "d"};

       qStableSort(str.begin(), str.end(), compare);

       qDebug() << str;

and compare:

    bool compare(const QString &str1, const QString &str2)
    {
        bool x = str1 > str2;
        qDebug() << x;
        return str1 > str2;
    }

the output is:

    true
    true
    true
    true
    true
    true

("d", "c", "b", "a")

I may be wrong, but i think that when qStableSort evaluates a > b, it returns false returns false, which makes qStableSort believe that it needs to switch the two, which causes the output "b", "a".

again this all based on a whim

Chris Kawa

Well, you took a corner case example - the input letters are sorted in lexicographical order.
Yes, in this case if you return "str1 < str2" it will not change the order at all and "str1 > str2" will exactly reverse it.

That's because in case of "str1 < str2" the following is true: a<b, b<c, c<d.
In case of "str1 > str2" the following is true: b<a, c<b, d<c, so it will swap every pair.

manny

ok, i think i understand, thanks, really appreciate it