446,159 Members | 1,002 Online Need help? Post your question and get tips & solutions from a community of 446,159 IT Pros & Developers. It's quick & easy.

# qsort() results: implementation dependent?

 P: n/a Hi everybody, suppose you have to order a list of integers which refer to points located in the 3D space. The compare() function is based on the distance that these points have with respect to the origin (0,0,0). So, using the standart qsort() function, I think this task should be accomplished as follows: qsort(int_vector, (size_t)no_of_points, sizeof(int), compare_function); where static int compare_function(void *b0, const void *b1) { double eps = 1e-6; int pnt0 = *((int *)b0); int pnt1 = *((int *)b1); double d0 = get_distance(pnt0); double d1 = get_distance(pnt1); double dd = d0 - d1; if(dd > eps) return 1; else if (dd < -eps) return -1; else return 0.; } The question is: why two different qsort() implementations (AIX and Linux) should give different results? In particular, the Linux implementation seems to fail to to find the right order. Any hint? Thanks Max Jun 28 '06 #1
8 Replies

 P: n/a "Max" writes: suppose you have to order a list of integers which refer to points located in the 3D space. The compare() function is based on the distance that these points have with respect to the origin (0,0,0). So, using the standart qsort() function, I think this task should be accomplished as follows: qsort(int_vector, (size_t)no_of_points, sizeof(int), compare_function); If you have a visible prototype for qsort(), the cast is unnecessary. where static int compare_function(void *b0, const void *b1) { double eps = 1e-6; int pnt0 = *((int *)b0); int pnt1 = *((int *)b1); double d0 = get_distance(pnt0); double d1 = get_distance(pnt1); double dd = d0 - d1; if(dd > eps) return 1; else if (dd < -eps) return -1; else return 0.; } The question is: why two different qsort() implementations (AIX and Linux) should give different results? In particular, the Linux implementation seems to fail to to find the right order. Any hint? The comparison function has to be consistent. You're returning 0 for points that are very close to each other but not actually equal. For example, given: x = 1.0e-6 y = 1.6e-6 z = 2.2e-6 you would report x == y, y == z, but x < z, which causes undefined behavior in qsort(). I suggest dropping eps and just doing a comparison: if (d0 < d1) return -1; else if (d0 == d1) return 0; else return 1; Some other oddities: Both parameters of compare_function should be const. "return 0.;" should be "return 0;". You're returning a floating-point zero, which will be converted to int, so it has the same effect, but it's cleaner just to return an int. -- Keith Thompson (The_Other_Keith) ks***@mib.org San Diego Supercomputer Center <*> We must do something. This is something. Therefore, we must do this. Jun 28 '06 #2

 P: n/a On Wed, 28 Jun 2006 00:13:47 -0700, Max wrote: Hi everybody, suppose you have to order a list of integers which refer to points located in the 3D space. The compare() function is based on the distance that these points have with respect to the origin (0,0,0). So, using the standart qsort() function, I think this task should be accomplished as follows: qsort(int_vector, (size_t)no_of_points, sizeof(int), compare_function); where static int compare_function(void *b0, const void *b1) { double eps = 1e-6; int pnt0 = *((int *)b0); int pnt1 = *((int *)b1); double d0 = get_distance(pnt0); double d1 = get_distance(pnt1); double dd = d0 - d1; if(dd > eps) return 1; else if (dd < -eps) return -1; else return 0.; } The question is: why two different qsort() implementations (AIX and Linux) should give different results? In particular, the Linux implementation seems to fail to to find the right order. Any hint? Thanks Max I'm not sure if this is specified for qsort but I've learnt not to use it unless the compare function really is an order, ie unless the compare function only returns 0 if the two arguments are identical. Otherwise, in may experience at least, qsort can fail spectacularly (cause a core dump), and anyway I'd suspect that if it returns the final order of the array, (ie the order of the elements that are all equal as fare as the compare is concerned) is not just implementation but phase-of-the-moon dependent if the compare can return non zero for two different arguments Could you perhaps extend your comparison, function, eg if two points are the same distance from the origin, compare x then y then z coordinates too? Duncan Jun 28 '06 #3

 P: n/a Duncan Muirhead schrieb: I'm not sure if this is specified for qsort but I've learnt not to use it unless the compare function really is an order, ie unless the compare function only returns 0 if the two arguments are identical. You are right, but how to accomplish with that if you are dealing with doubles? Such a routine is expected to order points belonging to two different surfaces which are related by a geometrical transformation (translation or rotation). Ordering them according to the distance from the origin should store the pairs in sequence and make simple to split the resulting ordered list in two vector. If you know other (cheap?) algorithms, I will try them... Otherwise, in may experience at least, qsort can fail spectacularly (cause a core dump), and anyway I'd suspect that if it returns the final order of the array, (ie the order of the elements that are all equal as fare as the compare is concerned) is not just implementation but phase-of-the-moon dependent if the compare can return non zero for two different arguments Could you perhaps extend your comparison, function, eg if two points are the same distance from the origin, compare x then y then z coordinates too? Duncan You are right and it is what the real code does. I gave an simpler example (already tried) to focus on the topic. Thanks Max Jun 28 '06 #4

 P: n/a Max wrote: Duncan Muirhead schrieb: I'm not sure if this is specified for qsort but I've learnt not to use it unless the compare function really is an order, ie unless the compare function only returns 0 if the two arguments are identical. You are right, but how to accomplish with that if you are dealing with doubles? If you know other (cheap?) algorithms, I will try them... Get rid of your epsilon and difference equations. You don't want to equate near values in an ordering function. That's a bad thing to do. If one number is just a smidgeon less than another, then what's your objection to ordering it first? static int compare_function(const void *b0, const void *b1) { int pnt0 = *((int *)b0); int pnt1 = *((int *)b1); double d0 = get_distance(pnt0); double d1 = get_distance(pnt1); return d1 > d0 ? -1 : d0 > d1; } -- pete Jun 28 '06 #5

 P: n/a Max wrote: [...] You are right and it is what the real code does. I gave an simpler example (already tried) to focus on the topic. The simpler version has a bug, as has already been explained. Now: Is that bug an artifact of the simplification process, or is it also present in the original? Oh, drat: my Ouija board is in the shop getting its phlogiston generator repaired ... -- Eric Sosman es*****@acm-dot-org.invalid Jun 28 '06 #6

 P: n/a > [...] The simpler version has a bug, as has already been explained. Now: Is that bug an artifact of the simplification process, or is it also present in the original? If you refer to the undefined behaviour, yes, I have tried to test the code dropping out eps. I have got a different point list but it is still wrong. As I have already explained above, I have the possibility to visually check if the point list is correct or not. The line return 0.; was just a typing error here. Bye Max Jun 28 '06 #7

 P: n/a "Max" writes: [...] The simpler version has a bug, as has already been explained. Now: Is that bug an artifact of the simplification process, or is it also present in the original? If you refer to the undefined behaviour, yes, I have tried to test the code dropping out eps. I have got a different point list but it is still wrong. As I have already explained above, I have the possibility to visually check if the point list is correct or not. How is it "wrong"? Are you sure your get_distance function is correct? Do the points that are mis-ordered have nearly identical distances? Are you sure you're invoking qsort() correctly? We can only point out flaws in code that you post. If you show us an actual program that exhibits the problem, we can help. If not, we can't guess. -- Keith Thompson (The_Other_Keith) ks***@mib.org San Diego Supercomputer Center <*> We must do something. This is something. Therefore, we must do this. Jun 28 '06 #8

 P: n/a How is it "wrong"? Are you sure your get_distance function is correct? Do the points that are mis-ordered have nearly identical distances? Are you sure you're invoking qsort() correctly? Yes, the functions works correctly and they have been tested extensively. The qsort() call is not an issue. We can only point out flaws in code that you post. If you show us an actual program that exhibits the problem, we can help. If not, we can't guess. I know what you mean, and you are right. Unfortunately the code is not free and I am not allowed to distribute it... Anyway, I will investigate better the "undefined behaviour" tip, since this should be the problem. Up to now the algorithm has been used with small lists and its application to larger vectors may results in such a strange behaviour. Thanks Max -- Keith Thompson (The_Other_Keith) ks***@mib.org San Diego Supercomputer Center <*> We must do something. This is something. Therefore, we must do this. Jun 30 '06 #9

### This discussion thread is closed

Replies have been disabled for this discussion. 