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

If array is indeed the base-address of a sequence of PointP, then your params are not setup correctly in your comparator. You're missing one level of indirection. — WhozCraig
– WhozCraig, Commented Dec 18, 2012 at 16:09

111111 · Accepted Answer · 2012-12-18 15:04:08Z

4

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

edited Dec 18, 2012 at 15:04

answered Dec 18, 2012 at 14:53

111111

16.3k6 gold badges49 silver badges64 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Yuval Cohen Over a year ago

I'm not allowed to use c++11 or vectors :-(

Yuval Cohen Over a year ago

and if i change void* to Point* then qsort() claims that the arguments don't match

111111 Over a year ago

:/, you can still use std::sort as I have shown in the first example.

111111 Over a year ago

@YuvalCohen I am suggesting you DON'T use std::qsort but std::sort.

Bart van Ingen Schenau · Accepted Answer · 2012-12-18 15:04:04Z

3

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

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).
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.

answered Dec 18, 2012 at 15:04

Bart van Ingen Schenau

15.9k4 gold badges34 silver badges42 bronze badges

Comments

likeToCode · Accepted Answer · 2012-12-18 14:59:17Z

1

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

answered Dec 18, 2012 at 14:59

likeToCode

3713 silver badges3 bronze badges

Comments

Jakir Hossain · Accepted Answer · 2012-12-18 15:01:48Z

0

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

answered Dec 18, 2012 at 15:01

Jakir Hossain

3901 gold badge4 silver badges16 bronze badges

Collectives™ on Stack Overflow

qsort for sorting an array of objects

4 Answers 4

Note

References

4 Comments

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

Note

References

4 Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related