CODEWITHSUNDEEP
c++
user3689963
user3689963

Reputation: 115

identical result qsort vs std::sort

Please excuse the brevity of the message.

I have an array of records. I want to sort it in descending order w.r.t. one of it's key. Records' key are not unique.

compare function of qsort:

int cmp(const record* rec1, const record* rec2) 
{
    return rec2->key - rec1->key;
}

compare function of std::sort: 

bool operator()(const record& rec1, const record& rec2) 
{
    return rec1.key > rec2.key;
}

Will both the version give identical result? I am not sure if sort/qsort behave same way when keys are equal.

Upvotes: 4

Views: 376

Answers (2)

AndyG
AndyG

Reputation: 41100

No. Neither of these sorts are guaranteed to be stable sorts. Elements that compare equal may not appear in the same order using either sort.

There is also nothing in [alg.sort] guaranteeing that they use the same algorithm/implementation of that algorithm. In fact, since C++11 std::sort is guaranteed to be O(n log n), whereas, despite its name std::qsort is not even guaranteed to be a Quick Sort, much less have any specific time complexity (Which means that Bogosort is a conforming qsort implementation)

Edit

Since in the comments you specify that you're using GCC and are interested if perhaps that platform uses the same sort, the answer remains "no".

For qsort, it comes from whatever libc your version of GCC uses.

  • FreeBSD's qsort.c admittedly also appears to be an Introsort implementation, although the code is not identical and it's hard to say outright if they'd give you the same result.

Upvotes: 2

nwp
nwp

Reputation: 9991

There is no such guarantee.

std::qsort:

If comp indicates two elements as equivalent, their order is unspecified.

std::sort:

The order of equal elements is not guaranteed to be preserved.

You need a stable sorting algorithm if the order of equal elements needs to be preserved. std::stable_sort is stable.

Alternatively just add more keys to sort by so that no elements compare equal.

Upvotes: 3

Related Questions