Skip to main content
gamedev.net
🔒 Locked

qsort()

Started by daniel_i_l Dec 17, 2005 at 3:55 PM 2 replies 600+ views
Original Post
daniel_i_l
daniel_i_l
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
"We've all heard that a million monkeys banging on a million typewriters will eventually reproduce the entire works of Shakespeare. Now, thanks to the internet, we know this is not true." -- Professor Robert Silensky
Conner McCloud
Conner McCloud
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
iMalc
iMalc
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.
daniel_i_l
daniel_i_l
Thanks it worked!!
"We've all heard that a million monkeys banging on a million typewriters will eventually reproduce the entire works of Shakespeare. Now, thanks to the internet, we know this is not true." -- Professor Robert Silensky

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.