qsort for sorting an array of objects

Question

I'm trying to use the qsort() to sort an array of object pointers (PointP = Point*) attached is the compare function and the sorting, The problem is that nothing happens and sorting doesn't occur.

int compareByAngleP(const void* elem1,const void* elem2) {
    PointP point1 = (PointP) elem1;
    PointP point2 = (PointP) elem2;
    if (abs(point1->getAngle() - point2->getAngle())>0.001)
    {
        return point1->getAngle() - point2->getAngle();
    }
    return  point1->getY() - point2->getY();
}

void sortArrayP(PointP* array, int size) {
    qsort(array,size, sizeof(PointP), compareByAngleP);
}

Answer 1

My advice would be to forget about std::qsort, favour plain old std::sort. Unlike std::qsort it is typesafe and in most implementations much faster.

std::sort(array, array+size, compareByAngleP);

And do rid of the void* in the compare function in favour of actual types.

Furthermore, if you are using C++11 and the array is local simply:

std::sort(std::begin(array), std::end(array), compareByAngleP);

Or even better just use a std::vector or other most approitaite container.

std::vector<Point> array { ... };
std::sort(array.begin(), array.end(), compareByAngleP);

Note

You may need to amend your comparison function so that it returns ​true if the first argument is less than the second. (or simply implement operator < for Point).

References

http://en.cppreference.com/w/cpp/algorithm/sort

http://en.cppreference.com/w/cpp/container/vector

Answer 2

There are several problems in your use of qsort and in your comparison function.

1. qsort will use memcpy (or similar) to re-order the elements of the array. If your Point type has a copy-constructor (or a member that has one), then using qsort on it is asking for trouble (it results in Undefined Behaviour).

2. Your compareByAngleP function is not suitable for sorting, because the relation it checks is not transitive. For example, if you have three points A, B and C, all with the same Y coordinate and respectively with the angles 10.000, 10.001 and 10.002, then compareByAngeP will indicate that A == B and B == C, but A != C, which can cause havoc for a sorting function.