Trouble Sorting a 2d struct Array in C

Question

I have a (150x150)2d array of structs that i'd like to sort in a row independent fashion. Because it is a struct, i do not believe (correct me if i'm wrong here) i cannot use qsort() or at least do not know how to due to the fact i'm paring structs and the element i am comparing is a double which goes against the compare prototype requirement of qsort(). At any rate i'd like to apply quicksort on

  struct my_struct {
    int x;
    int y;
    double d;
 };
void quicksort(struct my_struct* array,int start, int end)
{

struct my_struct key, Pivot;
int i,j,PivotPoint;
if(start< end)
{
    PivotPoint = (start+end)/2;
    theswap(&array[start], &array[PivotPoint]);
    key = array[start];
    i= start+1;
    j = end;
    while (i<=j)
    {
        while((i<=end) && (array[i].d <= key.d))
            ++i;
        while ((j>=start) && array[j].d> key.d) {
            --j;
            if (i<j) {
                theswap(&array[i], &array[j]);
            }
        }
    }
    theswap(&array[start], &array[j]);
    quicksort(array, start, j-1);
    quicksort(array, j+1, end);
    }
}
void theswap(struct my_struct *a, struct TourElement *b)
{
struct my_struct t;
t=*a; 
*a=*b;
*b=t;
}

in my main function i have something like this:

 for (i=0;i<150;++i)
   {
   for (j=0;j<150;++j)
   { 
    My_array[i][j].x = somethingUseful;
    My_Array[i][j].y = somethingEquallyUseful;
    My_Array[i][j].d = CalcD(somethingUseful,somethingEquallyUseful);
    }
    qsort(My_Array[i],150,sizeof(my_struct),compare);
   }


       int compare(struct my_struct a , struct my_struct b)
     {
          return a.d -b.d;
     }

When i execute quicksort, the application hangs, upon further investigation, there doesn't seem to be any elements in array within the quicksort function. (I added a for loop printf at the beginning of quicksort to itemize the struct's d values and nothing was printed)

Can anyone identify what i am doing wrong here? I'm getting no compile errors. And The "D"s are calculated correctly.

Vote to close: Asking strangers to spot errors in your code by inspection is not productive. You should identify (or at least isolate) the problem by using a debugger or print statements, and then come back with a more specific question. Incidentally, you can use qsort on arbitrary structs, there are lots of examples out there. — Oliver Charlesworth
– Oliver Charlesworth, Commented Mar 31, 2012 at 19:57
You can use qsort() (which doesn't necessarily apply the "quick sort" algorithm) with arrays of structs. For ease-of-use just pretend your two-dimensional array is uni-dimensional. — pmg
– pmg, Commented Mar 31, 2012 at 20:04
OI tried to use qsort() but it didn't actually sort. but at least it didn't hang. Going to edit code above. — TheNewM
– TheNewM, Commented Mar 31, 2012 at 20:23
I should note, that this is just a piece of a MPI program and honestly, do not know how to debug this with a debugger and as i mentionned earlier the prints didn't actually print. — TheNewM
– TheNewM, Commented Mar 31, 2012 at 20:24

ejrav · Accepted Answer · 2012-03-31 20:25:10Z

1

you can use std c qsort



void qsort( void *buf, size_t num, size_t size, int (*compare)(const void *, const void *) );

the compare function is something like this:



int my_struct_comp(const void *p1, const void *p2){
  my_struct *mp1 = (my_Struct*)p1;
  my_struct *mp2 = (my_Struct*)p2;

  return mp1->d - mp2->d;
}

than you can call qsort (where len is the length of the array)



qsort(myarray, len, sizeof(my_struct), &my_struct_cmp);

answered Mar 31, 2012 at 20:25

ejrav

561 silver badge3 bronze badges

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

1 Comment

TheNewM Over a year ago

Yes! thank you. My initial attempt din't have the & therefore not working. Kudos!

Collectives™ on Stack Overflow

Trouble Sorting a 2d struct Array in C

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related