CODEWITHSUNDEEP
c++sortingqsort
Yuval Cohen
Yuval Cohen

Reputation: 233

qsort for sorting an array of objects

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);
}

Upvotes: 4

Views: 3541

Answers (4)

111111
111111

Reputation: 16148

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

Upvotes: 4

Bart van Ingen Schenau
Bart van Ingen Schenau

Reputation: 15768

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.

Upvotes: 3

Jakir Hossain
Jakir Hossain

Reputation: 390

I think if you return bool instead of int from Compare function, then something different will happen.

Upvotes: 0

likeToCode
likeToCode

Reputation: 371

Following qsort reference (http://en.cppreference.com/w/cpp/algorithm/qsort) 3rd parameter of qsort should be 'size of each element in the array in bytes' so instead 

qsort(array,size, sizeof(PointP), compareByAngleP);

try

qsort(array,size, sizeof(PointP*), compareByAngleP);

Also you are implicity casting float to int (while returning value from comparing function). But:

(int)0.2 == 0

Upvotes: 1

Related Questions