Using qsort() for stable sort?

Question

I was trying to solve a problem in a online judge system: https://acm.cs.nthu.edu.tw/problem/11519/ It takes an integer n, followed with n lines of name and grade. the problem is to sort them out by grades using a stable sort algorithm. I use qsort() and giving the person's order in the compar() to stabilize the qsort(). Here is my code:

class People{
    public:
        char name[11];
        int grade;
        int order;
        void print(){ printf("%s %d\n", name, grade); }
};

int compar(const void *a, const void *b){
    People *A = (People*)a;
    People *B = (People*)b;
    if(A->grade > B->grade) return 1;
    else if(A->grade < B->grade) return -1;
    else if(A->order > B->order) return 1;
    else if(A->order < B->order) return -1;
}

int main(){
    int n;
    scanf("%d", &n);
    People *p = new People[n];
    for(int i=0;i<n;i++){
        scanf("%s %d", p[i].name, &p[i].grade);
        p[i].order = i;
    }
    qsort(p, n, sizeof(People), compar);
    for(int i=0;i<n;i++){
        p[i].print();
    }
}

in all of my test cases, it works without any problem, but the online judge keeps giving my submits four WAs(wrong answer). Can someone give me some clues about this? Many thanks!

Answer 1

There is actually nothing wrong with your intent in the comparison function, it's a perfectly valid solution to use original ordering to turn an unstable sort into a stable one.

So, why it's being rejected, I cannot tell for sure, at least without having access to the test data being used.

It's possible that the names may contain spaces which will screw up your input method but (1) that doesn't seem to be indicated by the test description; and (2) it would make the input much more difficult, at least for the level the assignment seems aimed at.

However, though you may consider it unlikely, there is the possibility that the sorting algorithm may at some point compare an object with itself. This means it will return some arbitrary value since you assume they will always be different, given the added order checking.

You should probably cater for that since the one rule you're meant to follow in the comparison function is consistency and that, if a > b then b < a. So, two rules, really :-)

In addition, one thing I would suggest is to minimise your use of the legacy-C stuff like printf and scanf where C++ provides better facilities.

To that end, I believe you'd be better off with:

#include <iostream>
#include <cstdlib>

struct People {
    char name[11];
    int grade;
    int order;
    void print() { std::cout << name << " " << grade << std::endl; }
};

int compar(const void *a, const void *b) {
    People *A = (People*)a;
    People *B = (People*)b;

    // Use grade if different.

    if (A->grade > B->grade) return 1;
    if (A->grade < B->grade) return -1;

    // Otherwise, use order, unique in different objects.

    if (A->order > B->order) return 1;
    if (A->order < B->order) return -1;

    // But cater for the possibility you may compare an object with itself.

    return 0;
}

int main() {
    int n;
    std::cin >> n;

    People *p = new People[n];

    for (int i = 0; i < n; i++) {
        std::cin >> p[i].name >> p[i].grade;
        p[i].order = i;
    }

    qsort(p, n, sizeof(People), compar);

    for (int i = 0; i < n; i++) {
        p[i].print();
    }
}

You might also even want to consider moving away from the legacy-C qsort since C++ provides stable sort built in, specifically the stable_sort found in <algorithm>.

Answer 2

It ends up that I missed a line in the description:

The input includes multiple test cases. In each test case, the first line contains one integer N.

After several approaches, I got it passed with the following code:

class People{
    public:
        char name[11];
        int grade;
        int order;
        void print(){
            printf("%s %d\n", name, grade);
        }
};

int compar(const void *a, const void *b){
    People *A = (People*)a;
    People *B = (People*)b;
    if(A->grade > B->grade) return 1;
    else if(A->grade < B->grade) return -1;
    else if(A->order > B->order) return 1;
    else if(A->order < B->order) return -1;
    return 0;
}

int main(){
    int n;
    while(scanf("%d", &n)!=EOF){
        People *p = new People[n];
        for(int i=0;i<n;i++){
            scanf("%s %d", p[i].name, &p[i].grade);
            p[i].order = i;
        }
        qsort(p, n, sizeof(People), compar);
        for(int i=0;i<n;i++){
            p[i].print();
        }
        delete[] p;
    }
}

std::stable_sort just works, However, it received TLE(Time Limit Exceeded),and the cin/cout causes TLE, too. So that's the reason I stick with printf/scanf.

Thanks everyone for answering this question! :)