How to sort an array of pointers to structure

This is a discussion on How to sort an array of pointers to structure within the C Programming forums, part of the General Programming Boards category; Hello, I need to sort an array of pointers to structures. The structure is as follows : Code: typedef struct ...

  1. #1
    Registered User
    Join Date
    Apr 2008
    Posts
    87

    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 ?

  2. #2
    int x = *((int *) NULL); Cactus_Hugger's Avatar
    Join Date
    Jul 2003
    Location
    Banks of the River Styx
    Posts
    902
    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.
    long time; /* know C? */
    Unprecedented performance: Nothing ever ran this slow before.
    Any sufficiently advanced bug is indistinguishable from a feature.
    Real Programmers confuse Halloween and Christmas, because dec 25 == oct 31.
    The best way to accelerate an IBM is at 9.8 m/s/s.
    recursion (re - cur' - zhun) n. 1. (see recursion)

  3. #3
    Registered User
    Join Date
    Apr 2008
    Posts
    87
    Quote Originally Posted by Cactus_Hugger View Post
    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]);

  4. #4
    Registered User
    Join Date
    Apr 2008
    Posts
    87
    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;
    }

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Array of Pointers to Arrays
    By Biozero in forum C Programming
    Replies: 2
    Last Post: 04-19-2007, 03:31 PM
  2. Replies: 4
    Last Post: 11-02-2006, 11:41 AM
  3. Creating an array of pointers to int[]
    By OkashiiKen in forum C Programming
    Replies: 3
    Last Post: 09-29-2006, 07:48 PM
  4. Returning an Array of Pointers to Objects
    By randomalias in forum C++ Programming
    Replies: 4
    Last Post: 04-29-2006, 03:45 PM
  5. Help with an Array
    By omalleys in forum C Programming
    Replies: 1
    Last Post: 07-01-2002, 09:31 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21