Sign in to follow this  

qsort()

This topic is 4383 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I'm trying to sort an array of units in the following way: -Find the unit in the middle -sort the units from closest (to the middle unit) to furthest. I used
middle_man = FindMiddle();
     qsort((void *) &unit, number_of_units, sizeof(struct unit), (compfn)CompareDisMid );

were the FindMiddle function finds the place in the array of the middle unit. That part works. For the compare I used:
int CompareDisMid(struct unit *elem1, struct unit *elem2)		 
{
   if(abs(elem1->current_step.x-unit[middle_man].current_step.x)+
      abs(elem1->current_step.y-unit[middle_man].current_step.y)
     <abs(elem2->current_step.x-unit[middle_man].current_step.x)+
      abs(elem2->current_step.y-unit[middle_man].current_step.y))		
      return -1;												
   else if(abs(elem1->current_step.x-unit[middle_man].current_step.x)+
           abs(elem1->current_step.y-unit[middle_man].current_step.y)
        >  abs(elem2->current_step.x-unit[middle_man].current_step.x)+
           abs(elem2->current_step.y-unit[middle_man].current_step.y))		
      return 1;													
   else											 return 0;	
    												
}

The problem is that it takes 2-3 time of calling qsort for it to work properly. For example, the middle_man should turn to 0 after one call right?! What is the problem? I think that the problem could be connected to the fact that during the qsort the middle_man changes. If so how do I fix it? Thanks a lot

Share this post


Link to post
Share on other sites
Indeed, your sort is going to change the value of unit[middle_man] is going to change over the course of your sort.

I can think of two ways around it. The first would involve copying your middle object rather than repeatedly checking the actual unit array. This has the added advantage of removing the dependancy on your unit array from your comparison function. The other would involve swapping unit[middle_man] with unit[0], and only sorting from unit[1] on. Or do both.

CM

Share this post


Link to post
Share on other sites
In other words, do this:
struct unit middle_man = unit[FindMiddle()]; // Copy the middle man
qsort((void *) &unit, number_of_units, sizeof(struct unit), (compfn)CompareDisMid );

int CompareDisMid(struct unit *elem1, struct unit *elem2)
{
if(abs(elem1->current_step.x-middle_man.current_step.x)+
abs(elem1->current_step.y-middle_man.current_step.y)
<abs(elem2->current_step.x-middle_man.current_step.x)+
abs(elem2->current_step.y-middle_man.current_step.y))
return -1;

else if(abs(elem1->current_step.x-middle_man.current_step.x)+
abs(elem1->current_step.y-middle_man.current_step.y)
> abs(elem2->current_step.x-middle_man.current_step.x)+
abs(elem2->current_step.y-middle_man.current_step.y))
return 1;

else
return 0;
}

You could of course do even better by just copying the current_step member of the struct, rather than the whole thing, but I don't know what type it is, so I'll leave that as an exersize for you.

Though I think you've written this example code as if 'unit' were both a type and your array name.

Share this post


Link to post
Share on other sites

This topic is 4383 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this