How to use qsort function of C library ?

P

pereges

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

Is qsort the best sorting algorithm out there ?
 
P

pereges

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.
 
K

Keith Thompson

pereges said:
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.)
 
K

Keith Thompson

pereges said:
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/>.
 
W

Willem

Walter wrote:
) In article <b7db2b94-9951-424c-83a6-b725fe54b002@z24g2000prf.googlegroups.com>,
)>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
 
C

Chris McDonald

'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.
 
P

pereges

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.
 
B

Ben Bacarisse

pereges said:
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.
 
P

pereges

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 ?
 
T

Thad Smith

pereges said:
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.
 
P

pereges

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.cen.x, kdroot->bhead.cen.y, kdroot->bhead.cen.z,

kdroot->bhead.r);*/
}
build_kdtree(kdroot, 0);
return kdroot;

}
 
P

pereges

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.cen.y, kdroot-
bhead.cen.z,kdroot->bhead.r);*/

}

build_kdtree(kdroot, 0);
return kdroot;

}
 
P

pereges

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);
 
W

Walter Roberson

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;
 
K

Keith Thompson

pereges said:
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.)
 
P

pereges

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.
 
B

Barry Schwarz

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
 

Ask a Question

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

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,744
Messages
2,569,483
Members
44,902
Latest member
Elena68X5

Latest Threads

Top