How to use qsort function of C library ?

Discussion in 'C Programming' started by pereges, Apr 8, 2008.

  1. pereges

    pereges Guest

    It is not explained well in my manual. can someone please tell me
    about it ?

    Is qsort the best sorting algorithm out there ?
     
    pereges, Apr 8, 2008
    #1
    1. Advertising

  2. pereges

    pereges Guest

    Re: How to use qsort function of C library ?

    I actually need to sort a set of vertices each having x, y, z
    coordinates but then I have to sort the records according to x
    coordinate, y coordinate or z.
     
    pereges, Apr 8, 2008
    #2
    1. Advertising

  3. In article <>,
    pereges <> wrote:
    >It is not explained well in my manual. can someone please tell me
    >about it ?


    >Is qsort the best sorting algorithm out there ?


    No.
    http://en.wikipedia.org/wiki/Sorting_algorithm

    Notice that the worst case for quick sort is O(n^2). There are a
    number of other algorithms listed there whose worst case is O(n*log(n))

    See also the mention of "Simple pancake sort", and of "Han's algorithm".

    --
    "The whole history of civilization is strewn with creeds and
    institutions which were invaluable at first, and deadly
    afterwards." -- Walter Bagehot
     
    Walter Roberson, Apr 8, 2008
    #3
  4. pereges <> writes:
    > It is not explained well in my manual. can someone please tell me
    > about it ?
    >
    > Is qsort the best sorting algorithm out there ?


    You appear to be the same person who's been posting as "broli".
    Please use a consistent name when posting here.

    Please put your question in the body of the message. Not all
    newsreaders show the subject header in a way that makes it easy to
    see.

    qsort is not an algorithm, it's an interface specified by the C
    standard. Different implementations of qsort can use different
    algorithms. (The name was originally derived from "quicksort", but
    there's no requirement for qsort to use the quicksort algorithm.)

    --
    Keith Thompson (The_Other_Keith) <>
    Nokia
    "We must do something. This is something. Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"
     
    Keith Thompson, Apr 8, 2008
    #4
  5. pereges <> writes:
    > It is not explained well in my manual. can someone please tell me
    > about it ?
    >
    > Is qsort the best sorting algorithm out there ?


    I forgot to mention, there are examples of using qsort() in section 13
    of the comp.lang.c FAQ, <http://www.c-faq.com/>.

    --
    Keith Thompson (The_Other_Keith) <>
    Nokia
    "We must do something. This is something. Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"
     
    Keith Thompson, Apr 8, 2008
    #5
  6. pereges

    Willem Guest

    Walter wrote:
    ) In article <>,
    ) pereges <> wrote:
    )>It is not explained well in my manual. can someone please tell me
    )>about it ?
    )
    )>Is qsort the best sorting algorithm out there ?
    )
    ) No.
    ) <snip>

    qsort, in this context, is not an algorithm. It *uses* an algorithm,
    but it's free for the implementor to decide which one (or ones).


    SaSW, Willem
    --
    Disclaimer: I am in no way responsible for any of the statements
    made in the above text. For all I know I might be
    drugged or something..
    No I'm not paranoid. You all think I'm paranoid, don't you !
    #EOT
     
    Willem, Apr 8, 2008
    #6
  7. Re: How to use qsort function of C library ?

    CBFalconer <> writes:

    >pereges wrote:
    >>
    >> It is not explained well in my manual. can someone please tell me
    >> about it ?


    >'it' is a pronoun, normally used to refer to a noun used earlier in
    >the paragraph.


    The noun appeared in the Subject: line,
    clearly referring to qsort and not the library.

    --
    Chris.
     
    Chris McDonald, Apr 9, 2008
    #7
  8. pereges

    pereges Guest

    Re: How to use qsort function of C library ?

    I think in this case I will be better of writing an sorting function
    of my own. my array is a buffer of vertices where each vertex is
    actually a struct having a x, y and z component. i need to sort the
    records according to x coordinate or y coordinate or z coordinate. i
    don't think you can use qsort to accomplish this.
     
    pereges, Apr 9, 2008
    #8
  9. Re: How to use qsort function of C library ?

    pereges <> writes:

    > I think in this case I will be better of writing an sorting function
    > of my own. my array is a buffer of vertices where each vertex is
    > actually a struct having a x, y and z component. i need to sort the
    > records according to x coordinate or y coordinate or z coordinate. i
    > don't think you can use qsort to accomplish this.


    I think you can. Do you mean sort by x sometimes and by y other
    times? If that is the case, you just need three comparison
    functions. You could have just one with a global "coordinate" picking
    variable, but the three function route is simpler.

    --
    Ben.
     
    Ben Bacarisse, Apr 9, 2008
    #9
  10. pereges

    pereges Guest

    Re: How to use qsort function of C library ?

    On Apr 9, 9:53 am, Richard Heathfield <> wrote:

    >
    > Well, actually you can, provided that you can define an ordering
    > relationship between two vertices. For example, let us say that we want to
    > order by x first, by y if x1==x2, and by z if x1==x2 and y1==y2. We do it
    > like this:
    >


    What is this ordering relationship ? Why should we sort along y if x1
    == x2 or z if x1 == x2 and
    y1 ==y2 ?
     
    pereges, Apr 9, 2008
    #10
  11. pereges

    Thad Smith Guest

    Re: How to use qsort function of C library ?

    pereges wrote:
    > On Apr 9, 9:53 am, Richard Heathfield <> wrote:
    >
    >> Well, actually you can, provided that you can define an ordering
    >> relationship between two vertices. For example, let us say that we want to
    >> order by x first, by y if x1==x2, and by z if x1==x2 and y1==y2. We do it
    >> like this:

    >
    > What is this ordering relationship ? Why should we sort along y if x1
    > == x2 or z if x1 == x2 and
    > y1 ==y2 ?


    The ordering Richard specified was an example of what could be done. The
    point is that you can define whatever ordering you want to use for sorting.

    --
    Thad
     
    Thad Smith, Apr 9, 2008
    #11
  12. pereges

    pereges Guest

    Re: How to use qsort function of C library ?

    What I am actually doing is for my kdtree program. I have an object
    which I want to divide spatially using kdtrees. There is bounding box
    for an entire object. I also built a bounding sphere for every
    triangle and then based on the centers of these bounding spheres, I
    will calculate a median. At this point the box must be split into left
    and right child boxes. Now, the splitting axis which is used to
    subdivide a bounding box will depend on depth.
    axis = depth % 3

    suppose axis ==0 then the box will be split along x axis and the
    median center is taken as the split point. If axis == 1 then split
    along y axis, if axis == 2 then split along z axis. To cacluate
    median, I need to sort the list of bounding spheres within a
    particular kd tree node/box. I will sort this list (along x, y ,
    z)depending upon value of axis.



    In the below a triangle is

    typedef struct triangle_struct
    {
    int v0, v1, v2; /* 3 indices into vertex list that identify a
    triangle */
    }triangle;

    typedef vector vertex; /* vertex is a vector of doubles */

    Object is

    typedef struct object_struct
    {
    int ntri, nvert; /* number of triangles and no of vertices
    respectively */
    triangle *tri; /* list of triangles */
    vertex *vert; /* vertex list */
    } object;


    kdtree.h
    ----------------------------------------

    #ifndef kd_tree
    #define kd_tree

    #include "common.h"
    #include "reader.h"

    typedef struct bounding_sphere_struct
    {
    vector cen; /*center of bounding sphere */
    double r; /* radius */
    int tid; /* id of triangle inside this sphere */
    triangle tr; /* triangle in this sphere */

    }bsphere;


    typedef struct kdnode_struct
    {
    vector maxB, minB; /* maximum bound of the kdnode/box , minimum bound
    */
    vector split; /* point along which this box will be split */
    struct kdnode_struct *left, *right; /* left child right child */
    bsphere* bhead; /* list of bounding spheres inside this box */
    int maxspheres; /* Maximum number of spheres in this box */

    }kdnode;

    int compute_bounding_sphere(bsphere *bs, vector a, vector b, vector
    c);
    kdnode* init_kdtree(object *, kdnode *);
    void build_kdtree(kdnode *kd, int depth);
    #endif


    kdtree.c
    --------------------------------------------

    #include "kdtree.h"

    int axis = 0;

    /* this function runs correctly, as i have checked it */
    int compute_bounding_sphere(bsphere *bs, vector a, vector b, vector c)
    {
    double dotABAB, dotABAC, dotACAC, d,s ,t ;
    vector tp, temp1, temp2;

    vector_sub(&b, &a, &temp1);
    dotABAB = vector_dot( &temp1, &temp1);
    vector_sub(&c, &a, &temp2);
    dotABAC = vector_dot(&temp1, &temp2);
    dotACAC = vector_dot(&temp2, &temp2);
    d = 2.0 *(dotABAB*dotACAC - dotABAC*dotABAC);

    if (fabs(d) <= 0)
    return FAILURE;
    s = (dotABAB*dotACAC - dotACAC*dotABAC) / d;
    t = (dotACAC*dotABAB - dotABAB*dotABAC) / d;
    tp = c;
    /* s controls height over AC, t over AB, (1-s-t) over BC */
    if (s <= 0.0)
    {
    bs->cen.x = 0.5*(a.x + c.x);
    bs->cen.y = 0.5* (a.y + c.y);
    bs->cen.z = 0.5* (a.z + c.z);
    }
    else
    if (t <= 0.0)
    {
    bs->cen.x = 0.5 *(a.x + b.x);
    bs->cen.y = 0.5 * (a.y + b.y);
    bs->cen.z = 0.5* (a.z + b.z);
    }
    else
    if (s + t >= 1.0)
    {
    bs->cen.x = 0.5*(b.x + c.x);
    bs->cen.y = 0.5 * (b.y + c.y);
    bs->cen.z = 0.5*(b.z + c.z);

    }
    else
    {
    bs->cen.x = a.x + s*(b.x - a.x) + t*(c.x - a.x);
    bs->cen.y = a.y + s*(b.y - a.y)+ t*(c.y - a.y);
    bs->cen.z = a.z + s* (b.z - a.z)+t*(c.z - a.z);
    }
    vector_sub(&(bs->cen), &tp, &temp1);
    bs->r = sqrt( vector_dot(&temp1, &temp1));
    return SUCCESS;
    }


    /* this is incomplete */
    void sort_x(kdnode *kd)
    {
    int i, j;
    for(i=0; i < kd->maxspheres; i++)
    for(j=0; j<

    }

    /* this is incomplete */
    void sort_y(kdnode *kd)
    {

    }


    /* this is incomplete */

    void sort_z(kdnode *kd)
    {

    }

    /* this is incomplete as well but i will make it a recursive function
    probably
    void build_kdtree(kdnode *kd, int depth)
    {
    int median;
    if(kd->maxspheres <= MINSPHERES || depth < DEPTHLIMIT)
    {
    kd->left = kd->right = NULL;
    return;
    }

    else
    {

    if(axis == 0) /* sort kdnode->bhead along x axis, find the
    median and use it to split */
    {
    }

    if(axis == 1)/* sort kdnode->bhead along x axis, find the
    median and use it to split */
    {
    }

    if(axis == 2)/* sort kdnode->bhead along x axis, find the
    median and use it to split */
    {

    }

    build_kdtree(kdnode->left, depth+1);
    build_kdtree(kdnode->right, depth+1);

    }



    /* Initializes the root node of the kdtree */
    kdnode* init_kdtree(object *o, kdnode *kdroot)
    {
    int i,flag;
    flag = FAILURE;
    kdroot = malloc(sizeof(kdnode));
    kdroot->left = kdroot->right = NULL;
    kdroot->maxB.x = kdroot->maxB.y = kdroot->maxB.z = -DBL_MAX;
    kdroot->minB.x = kdroot->minB.y = kdroot->minB.z = DBL_MAX;
    for(i = 0; i<o->nvert; i++)
    {
    if(o->vert.x <kdroot-> minB.x)
    kdroot->minB.x = o->vert.x;
    if(o->vert.x > kdroot->maxB.x)
    kdroot->maxB.x = o->vert.x;
    if(o->vert.y < kdroot->minB.y)
    kdroot->minB.y = o->vert.y;
    if(o->vert.y > kdroot->maxB.y)
    kdroot->maxB.y = o->vert.y;
    if(o->vert.z < kdroot->minB.z)
    kdroot->minB.z = o->vert.z;
    if(o->vert.z > kdroot->maxB.z)
    kdroot->maxB.z = o->vert.z;
    }

    /*printf("MAXB: %f %f %f MINB: %f %f %f \n", kdroot-
    >maxB.x, kdroot->maxB.y, kdroot->maxB.z, kdroot->minB.x, kdroot-
    >minB.y, kdroot->minB.z); */

    kdroot->bhead = calloc(sizeof(bsphere), o->ntri);
    kdroot->maxspheres = o->ntri;
    for(i=0; i<o->ntri; i++)
    {
    flag = compute_bounding_sphere(&(kdroot->bhead), o-
    >vert[o->tri.v0], o->vert[o->tri.v1], o->vert[o->tri.v2]);

    if(flag == FAILURE)
    {
    printf("Error in calculation of bounding spheres\n");
    exit(FAILURE);
    }
    kdroot->bhead.tr = o->tri;
    kdroot->bhead.tid = i;
    /*printf("Flag:%d Center:%f %f %f radius: %f\n",flag, kdroot-
    >bhead[i].cen.x, kdroot->bhead[i].cen.y, kdroot->bhead[i].cen.z,[/i][/i][/i]
    [i][i]
    kdroot->bhead[i].r);*/
    }
    build_kdtree(kdroot, 0);
    return kdroot;

    }[/i][/i][/i]
     
    pereges, Apr 9, 2008
    #12
  13. pereges

    pereges Guest

    Re: How to use qsort function of C library ?

    What I am actually doing is for my kdtree program. I have an object
    which I want to divide spatially using kdtrees. There is bounding box
    for an entire object. I also built a bounding sphere for every
    triangle and then based on the centers of these bounding spheres, I
    will calculate a median. At this point the box must be split into left
    and right child boxes. Now, the splitting axis which is used to
    subdivide a bounding box will depend on depth.
    axis = depth % 3

    suppose axis ==0 then the box will be split along x axis and the
    median center is taken as the split point. If axis == 1 then split
    along y axis, if axis == 2 then split along z axis. To cacluate
    median, I need to sort the list of bounding spheres within a
    particular kd tree node/box. I will sort this list (along x, y ,
    z)depending upon value of axis.

    My code -

    In the below a triangle is

    typedef struct triangle_struct
    {
    int v0, v1, v2; /* 3 indices into vertex list that identify a
    triangle */

    }triangle;

    typedef vector vertex; /* vertex is a vector of doubles */

    Object is

    typedef struct object_struct
    {
    int ntri, nvert; /* number of triangles and no of vertices
    respectively */
    triangle *tri; /* list of triangles */
    vertex *vert; /* vertex list */

    } object;




    kdtree.h
    ----------------------------------------

    #ifndef kd_tree
    #define kd_tree

    #include "common.h"
    #include "reader.h"

    typedef struct bounding_sphere_struct
    {
    vector cen; /*center of bounding sphere */
    double r; /* radius */
    int tid; /* id of triangle inside this sphere */
    triangle tr; /* triangle in this sphere */

    }bsphere;

    typedef struct kdnode_struct
    {
    vector maxB, minB; /* maximum bound of the kdnode/box ,
    minimum bound*/
    vector split; /* point along which this box will be split */
    struct kdnode_struct *left, *right; /* left child right child
    */
    bsphere* bhead; /* list of bounding spheres inside this box */
    int maxspheres; /* Maximum number of spheres in this box */

    }kdnode;

    int compute_bounding_sphere(bsphere *bs, vector a, vector b, vector
    c);
    kdnode* init_kdtree(object *, kdnode *);
    void build_kdtree(kdnode *kd, int depth);

    #endif

    kdtree.c
    --------------------------------------------

    #include "kdtree.h"

    int axis = 0;

    /* this function runs correctly, as i have checked it */
    int compute_bounding_sphere(bsphere *bs, vector a, vector b, vector c)
    {
    double dotABAB, dotABAC, dotACAC, d,s ,t ;
    vector tp, temp1, temp2;

    vector_sub(&b, &a, &temp1);
    dotABAB = vector_dot( &temp1, &temp1);
    vector_sub(&c, &a, &temp2);
    dotABAC = vector_dot(&temp1, &temp2);
    dotACAC = vector_dot(&temp2, &temp2);
    d = 2.0 *(dotABAB*dotACAC - dotABAC*dotABAC);

    if(fabs(d) <= 0)
    return FAILURE;
    s = (dotABAB*dotACAC - dotACAC*dotABAC) / d;
    t = (dotACAC*dotABAB - dotABAB*dotABAC) / d;
    tp = c;
    /* s controls height over AC, t over AB, (1-s-t) over BC */
    if (s <= 0.0)
    {
    bs->cen.x = 0.5*(a.x + c.x);
    bs->cen.y = 0.5* (a.y + c.y);
    bs->cen.z = 0.5* (a.z + c.z);
    }
    else
    if (t <= 0.0)
    {
    bs->cen.x = 0.5 *(a.x + b.x);
    bs->cen.y = 0.5 * (a.y + b.y);
    bs->cen.z = 0.5* (a.z + b.z);
    }
    else
    if (s + t >= 1.0)
    {
    bs->cen.x = 0.5*(b.x + c.x);
    bs->cen.y = 0.5 * (b.y + c.y);
    bs->cen.z = 0.5*(b.z + c.z);

    }
    else
    {
    bs->cen.x = a.x + s*(b.x - a.x) + t*(c.x - a.x);
    bs->cen.y = a.y + s*(b.y - a.y)+ t*(c.y - a.y);
    bs->cen.z = a.z + s* (b.z - a.z)+t*(c.z - a.z);
    }
    vector_sub(&(bs->cen), &tp, &temp1);
    bs->r = sqrt( vector_dot(&temp1, &temp1));
    return SUCCESS;
    }

    /* this is incomplete */
    void sort_x(kdnode *kd)
    {


    }

    /* this is incomplete */
    void sort_y(kdnode *kd)
    {

    }

    /* this is incomplete */

    void sort_z(kdnode *kd)
    {

    }

    /* this is incomplete as well but i will make it a recursive function
    probably
    void build_kdtree(kdnode *kd, int depth)
    {
    int median;
    if(kd->maxspheres <= MINSPHERES || depth < DEPTHLIMIT)
    {
    kd->left = kd->right = NULL;
    return;
    }

    else
    {

    if(axis == 0) /* sort kdnode->bhead along x axis, find the
    median and use it to split */
    {

    }

    if(axis == 1)/* sort kdnode->bhead along x axis, find the
    median and use it to split */
    {

    }

    if(axis == 2)/* sort kdnode->bhead along x axis, find the
    median and use it to split */
    {

    }

    build_kdtree(kdnode->left, depth+1);
    build_kdtree(kdnode->right, depth+1);

    }

    /* Initializes the root node of the kdtree */
    kdnode* init_kdtree(object *o, kdnode *kdroot)
    {
    int i,flag;
    flag = FAILURE;
    kdroot = malloc(sizeof(kdnode));
    kdroot->left = kdroot->right = NULL;
    kdroot->maxB.x = kdroot->maxB.y = kdroot->maxB.z = -DBL_MAX;
    kdroot->minB.x = kdroot->minB.y = kdroot->minB.z = DBL_MAX;
    for(i = 0; i<o->nvert; i++)
    {
    if(o->vert.x <kdroot-> minB.x)
    kdroot->minB.x = o->vert.x;
    if(o->vert.x > kdroot->maxB.x)
    kdroot->maxB.x = o->vert.x;
    if(o->vert.y < kdroot->minB.y)
    kdroot->minB.y = o->vert.y;
    if(o->vert.y > kdroot->maxB.y)
    kdroot->maxB.y = o->vert.y;
    if(o->vert.z < kdroot->minB.z)
    kdroot->minB.z = o->vert.z;
    if(o->vert.z > kdroot->maxB.z)
    kdroot->maxB.z = o->vert.z;
    }

    /*printf("MAXB: %f %f %f MINB: %f %f %f \n", kdroot-
    >maxB.x, kdroot->maxB.y, kdroot->maxB.z, kdroot->minB.x, kdroot-
    >minB.y, kdroot->minB.z); */


    kdroot->bhead = calloc(sizeof(bsphere), o->ntri);
    kdroot->maxspheres = o->ntri;
    for(i=0; i<o->ntri; i++)
    {
    flag = compute_bounding_sphere(&(kdroot->bhead), o-
    >vert[o->tri.v0], o->vert[o->tri.v1], o->vert[o->tri.v2]);


    if(flag == FAILURE)
    {
    printf("Error in calculation of bounding
    spheres\n");
    exit(FAILURE);
    }
    kdroot->bhead.tr = o->tri;
    kdroot->bhead.tid = i;
    /*printf("Flag:%d Center:%f %f %f radius: %f\n",flag,
    kdroot->bhead.cen.x, kdroot->bhead[i].cen.y, kdroot-[color=blue]
    >bhead[i].cen.z,kdroot->bhead[i].r);*/[/i][/i][/color][i][i]
    }

    build_kdtree(kdroot, 0);
    return kdroot;

    }[/i][/i][/i]
     
    pereges, Apr 9, 2008
    #13
  14. pereges

    pereges Guest

    Re: How to use qsort function of C library ?

    This is too complicated. I have to sort the array of structures given
    by kd->bhead pointer according to the x coordinate of center. kd-
    >bhead.cen.x. I wonder if something like below would work -




    void cmpcenter_x(const void *cpa, const void *cpb)
    {
    const bsphere *ca = cpa;
    const bsphere *cb = cpb;

    return(ca->cen.x - cb.cen.x);
    }

    ...................
    ...................

    qsort(kd->bhead, kd->maxspheres, sizeof(bsphere), cmpcenter_x);
     
    pereges, Apr 9, 2008
    #14
  15. Re: How to use qsort function of C library ?

    In article <>,
    pereges <> wrote:
    >This is too complicated. I have to sort the array of structures given
    >by kd->bhead pointer according to the x coordinate of center. kd-
    >>bhead.cen.x. I wonder if something like below would work -


    >void cmpcenter_x(const void *cpa, const void *cpb)
    >{
    > const bsphere *ca = cpa;
    > const bsphere *cb = cpb;
    >
    > return(ca->cen.x - cb.cen.x);
    > }


    You probably meant cb->cen.x

    You don't -need- to assign the pointers. It might not make any
    difference with a good optimizer, but it might:

    return ((const bsphere *)ca)->cen.x - ((const bsphere *)cb)->cen.x;

    --
    "They called it golf because all the other four letter words
    were taken." -- Walter Hagen
     
    Walter Roberson, Apr 9, 2008
    #15
  16. Re: How to use qsort function of C library ?

    pereges <> writes:
    > This is too complicated. I have to sort the array of structures given
    > by kd->bhead pointer according to the x coordinate of center. kd-
    >>bhead.cen.x. I wonder if something like below would work -

    >
    > void cmpcenter_x(const void *cpa, const void *cpb)
    > {
    > const bsphere *ca = cpa;
    > const bsphere *cb = cpb;
    >
    > return(ca->cen.x - cb.cen.x);
    > }
    >
    > ..................
    > ..................
    >
    > qsort(kd->bhead, kd->maxspheres, sizeof(bsphere), cmpcenter_x);


    Using a subtraction like that:

    return ca->cen.x - cb->cen.x;

    is a cute trick, but you should avoid it unless you're *certain* that
    it can't overflow (or wrap around if x is unsigned).

    A more straightforward test is:

    if (ca->cen.x < cb->cen.x) {
    return -1;
    }
    else if (ca->cen.x > cb->cen.x) {
    return 1;
    }
    else {
    return 0;
    }

    Or, if you like terseness:

    return ca->cen.x < cb->cen.x ? -1 : ca->cen.x > cb->cen.x;

    (This takes advantage of the fact that ">" yields 0 or 1.)

    --
    Keith Thompson (The_Other_Keith) <>
    Nokia
    "We must do something. This is something. Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"
     
    Keith Thompson, Apr 9, 2008
    #16
  17. pereges

    pereges Guest

    Re: How to use qsort function of C library ?

    On Apr 9, 12:59 pm, Keith Thompson <> wrote:
    > Using a subtraction like that:
    >
    > return ca->cen.x - cb->cen.x;
    >
    > is a cute trick, but you should avoid it unless you're *certain* that
    > it can't overflow (or wrap around if x is unsigned).
    >
    > A more straightforward test is:
    >
    > if (ca->cen.x < cb->cen.x) {
    > return -1;
    > }
    > else if (ca->cen.x > cb->cen.x) {
    > return 1;
    > }
    > else {
    > return 0;
    > }
    >
    > Or, if you like terseness:
    >
    > return ca->cen.x < cb->cen.x ? -1 : ca->cen.x > cb->cen.x;
    >
    > (This takes advantage of the fact that ">" yields 0 or 1.)
    >


    I don't think it will work with kdnode->bhead.cen.x

    You are trying to sort an array bhead[0..maxspheres] according to x of
    center element. Probably, qsort will not give results with comparison
    functions like the one above.
     
    pereges, Apr 9, 2008
    #17
  18. Re: How to use qsort function of C library ?

    On Wed, 9 Apr 2008 01:39:55 -0700 (PDT), pereges <>
    wrote:

    >On Apr 9, 12:59 pm, Keith Thompson <> wrote:
    >> Using a subtraction like that:
    >>
    >> return ca->cen.x - cb->cen.x;
    >>
    >> is a cute trick, but you should avoid it unless you're *certain* that
    >> it can't overflow (or wrap around if x is unsigned).
    >>
    >> A more straightforward test is:
    >>
    >> if (ca->cen.x < cb->cen.x) {
    >> return -1;
    >> }
    >> else if (ca->cen.x > cb->cen.x) {
    >> return 1;
    >> }
    >> else {
    >> return 0;
    >> }
    >>
    >> Or, if you like terseness:
    >>
    >> return ca->cen.x < cb->cen.x ? -1 : ca->cen.x > cb->cen.x;
    >>
    >> (This takes advantage of the fact that ">" yields 0 or 1.)
    >>

    >
    >I don't think it will work with kdnode->bhead.cen.x
    >
    >You are trying to sort an array bhead[0..maxspheres] according to x of
    >center element. Probably, qsort will not give results with comparison
    >functions like the one above.
    >

    YOU need to examine the code. By the time your comparison function
    gets called, you only have two elements to compare and it doesn't
    matter how qsort decided which two.

    You originally started with
    return(ca->cen.x - cb.cen.x);
    Assuming integer values, this will return a negative value when the
    first term is less than the second, a positive value when the first is
    greater, and zero when both are the same.

    Both Keith's and Richard's suggestions do the SAME but eliminate the
    assumption about integers. Your code fails to sort properly for
    floating point values that differ by less than one due to truncation
    when the floating point result is converted to an integer as the
    return type. Since you are talking about coordinates, this may be
    significant.


    Remove del for email
     
    Barry Schwarz, Apr 9, 2008
    #18
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Debashish Chakravarty

    [possibly OT] the comparison function in qsort

    Debashish Chakravarty, Nov 23, 2003, in forum: C Programming
    Replies:
    0
    Views:
    318
    Debashish Chakravarty
    Nov 23, 2003
  2. Angus Comber
    Replies:
    7
    Views:
    1,164
    Richard Heathfield
    Feb 5, 2004
  3. Eddy C

    How would you use qsort to sort on a string

    Eddy C, Feb 9, 2006, in forum: C Programming
    Replies:
    31
    Views:
    1,790
    Jordan Abel
    Feb 13, 2006
  4. , India

    question on qsort library function

    , India, Mar 3, 2007, in forum: C Programming
    Replies:
    14
    Views:
    618
  5. Albert
    Replies:
    18
    Views:
    2,897
    user923005
    Sep 18, 2009
Loading...

Share This Page