Thread: How to sort an array of pointers to structure

Hello, I need to sort an array of pointers to structures. The structure is as follows :

Code:

typedef struct vector
{
   double coord[3];
};

The array has to sorted based on some condition. We compare either the coord[0] values , coord[1] values or coord[2] values. So I wrote three functions.

Code:

int cmp_coord_x(const void *vpa, const void *vpb)
{
    const vector *va = vpa;
    const vector *vb = vpb;

     return (va->coord[0] < va->coord[0] ? -1 : vb->coord[0] > vb->coord[0]); 
}

int cmp_coord_y(const void *vpa, const void *vpb)
{
    const vector *va = vpa;
    const vector *vb = vpb;

    return (va->coord[1] < va->coord[1] ? -1 : vb->coord[1] > vb->coord[1]); 
}

int cmp_coord_z(const void *vpa, const void *vpb)
{
    const vector *va = vpa;
    const vector *vb = vpb;

    return (va->coord[2] < va->coord[2] ? -1 : vb->coord[2] > vb->coord[2]); 
}

Now let's say the array of pointers is pointed to by parent_vpa. So I wrote :

Code:

   /* axis is used as criterion on how we sort the array */
    if (axis == 0)
   {
     qsort(parent_vpa, sizeof parent_vpa/ sizeof *parent_vpa, sizeof *parent_vpa, 
  cmp_coord_x);
   }
    if (axis == 1)
    {
         qsort(parent_vpa, sizeof parent_vpa/ sizeof *parent_vpa, sizeof *parent_vpa, 
  cmp_coord_y);
    }
    if (axis == 2)
    {
       qsort(parent_vpa, sizeof parent_vpa/ sizeof *parent_vpa, sizeof *parent_vpa, 
  cmp_coord_z);
    }

I'm still getting the unsorted list. Have I made a mistake somewhere ?

Originally Posted by Cactus_Hugger

in cmp_coord_*:

Code:

va->coord[0] < va->coord[0]

Always false. (Note: you do this several times)

Edit: in fact, all of your cmp_coord functions confuse me, but they all seem to have one possible output and no side effects.

you are right. it should be :

return (va->coord[0] < vb->coord[0] ? -1 : vb->coord[0] > va->coord[0]);

I also have another question. I tried writing a seperate quicksort implementation that sorts an array of pointers to such vector structs I described above. For some reason this program fails and terminates abnoramlly when left, right, i and j are data type size_t or unsigned long. What could be the reason ? Can I modify the program to make it work for size_t ? With long it seems to work fine and gives correct results.

Code:

void quicksort(vector **parent_vpa,  long left,  long right, int axis)
{
    long i, j;
    vector *pivotpoint;
    vector *tempstore;

    if (left < right)
    {
        i = left;
        j = right;

        pivotpoint = parent_vpa[(left+right)/2];
    
        while (i <= j)
        {
            while (parent_vpa[i]->coord[axis] < pivotpoint->coord[axis])
            {
                i++;
            }

            while (parent_vpa[j]->coord[axis] > pivotpoint->coord[axis])
            {
                j--;
            }
    
            if (i <= j)
            {
                tempstore = parent_vpa[i];
                parent_vpa[i] = parent_vpa[j];
                parent_vpa[j] = tempstore;
                i++;
                j--;              
            }
        }

        if (left < j)
        {
            quicksort(parent_vpa, left, j, axis);
        }
    
        if (i < right)
        {
            quicksort(parent_vpa, i, right, axis);
        }
    }
    else
        return;
}