468,512 Members | 1,454 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 468,512 developers. It's quick & easy.

How to use qsort function of C library ?

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

Is qsort the best sorting algorithm out there ?
Apr 8 '08 #1
16 4239
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.
Apr 8 '08 #2
pereges <Br*****@gmail.comwrites:
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) <ks***@mib.org>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
Apr 8 '08 #3
pereges <Br*****@gmail.comwrites:
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) <ks***@mib.org>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
Apr 8 '08 #4
Walter wrote:
) In article <b7**********************************@z24g2000prf. googlegroups.com>,
) pereges <Br*****@gmail.comwrote:
)>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
Apr 8 '08 #5
"Willem" <wi****@stack.nlwrote in message
news:sl********************@snail.stack.nl...
Walter wrote:
) In article
<b7**********************************@z24g2000prf. googlegroups.com>,
) pereges <Br*****@gmail.comwrote:
)>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).
Be that as it may, with the qsort() interface, it is not possible to
implement radix sorting, which (for small keys and large problem sizes) is
more efficient than comparison based sorting. Of course, there is no such
thing as the best sorting algorithm in general, because every algorithm has
some strengths and weaknesses.

Of course, your point is entirely correct. I just wanted to point out the
nuance that it is literally impossible for qsort() to always be the best
sorting algorithm for arbitrary inputs.
** Posted from http://www.teranews.com **
Apr 8 '08 #6
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.
>
Is qsort the best sorting algorithm out there ?
No. Under some cases.

--
[mail]: Chuck F (cbfalconer at maineline dot net)
[page]: <http://cbfalconer.home.att.net>
Try the download section.
** Posted from http://www.teranews.com **
Apr 9 '08 #7
CBFalconer <cb********@yahoo.comwrites:
>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.
Apr 9 '08 #8
Chris McDonald wrote:
CBFalconer <cb********@yahoo.comwrites:
>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,
So? I answered the question.

--
[mail]: Chuck F (cbfalconer at maineline dot net)
[page]: <http://cbfalconer.home.att.net>
Try the download section.
** Posted from http://www.teranews.com **
Apr 9 '08 #9
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.
Apr 9 '08 #10
pereges <Br*****@gmail.comwrites:
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.
Apr 9 '08 #11
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[i].x <kdroot-minB.x)
kdroot->minB.x = o->vert[i].x;
if(o->vert[i].x kdroot->maxB.x)
kdroot->maxB.x = o->vert[i].x;
if(o->vert[i].y < kdroot->minB.y)
kdroot->minB.y = o->vert[i].y;
if(o->vert[i].y kdroot->maxB.y)
kdroot->maxB.y = o->vert[i].y;
if(o->vert[i].z < kdroot->minB.z)
kdroot->minB.z = o->vert[i].z;
if(o->vert[i].z kdroot->maxB.z)
kdroot->maxB.z = o->vert[i].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[i]), o-
>vert[o->tri[i].v0], o->vert[o->tri[i].v1], o->vert[o->tri[i].v2]);
if(flag == FAILURE)
{
printf("Error in calculation of bounding spheres\n");
exit(FAILURE);
}
kdroot->bhead[i].tr = o->tri[i];
kdroot->bhead[i].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,
kdroot->bhead[i].r);*/
}
build_kdtree(kdroot, 0);
return kdroot;

}

Apr 9 '08 #12
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[i].x <kdroot-minB.x)
kdroot->minB.x = o->vert[i].x;
if(o->vert[i].x kdroot->maxB.x)
kdroot->maxB.x = o->vert[i].x;
if(o->vert[i].y < kdroot->minB.y)
kdroot->minB.y = o->vert[i].y;
if(o->vert[i].y kdroot->maxB.y)
kdroot->maxB.y = o->vert[i].y;
if(o->vert[i].z < kdroot->minB.z)
kdroot->minB.z = o->vert[i].z;
if(o->vert[i].z kdroot->maxB.z)
kdroot->maxB.z = o->vert[i].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[i]), o-
>vert[o->tri[i].v0], o->vert[o->tri[i].v1], o->vert[o->tri[i].v2]);
if(flag == FAILURE)
{
printf("Error in calculation of bounding
spheres\n");
exit(FAILURE);
}
kdroot->bhead[i].tr = o->tri[i];
kdroot->bhead[i].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,kdroot->bhead[i].r);*/
}

build_kdtree(kdroot, 0);
return kdroot;

}

Apr 9 '08 #13
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[i].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);
Apr 9 '08 #14
pereges <Br*****@gmail.comwrites:
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[i].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) <ks***@mib.org>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
Apr 9 '08 #15
Keith Thompson said:

<snip>
>
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.)
So does:

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

which is, of course, prettier. :-)

--
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999
Apr 9 '08 #16
On Apr 9, 12:59 pm, Keith Thompson <ks...@mib.orgwrote:
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[i].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.
Apr 9 '08 #17

This discussion thread is closed

Replies have been disabled for this discussion.

Similar topics

34 posts views Thread by richard | last post: by
11 posts views Thread by William Buch | last post: by
5 posts views Thread by Steve | last post: by
13 posts views Thread by buda | last post: by
16 posts views Thread by t_pantel | last post: by
14 posts views Thread by subramanian100in | last post: by
5 posts views Thread by subramanian100in | last post: by
10 posts views Thread by gauss010 | last post: by
17 posts views Thread by Ron Ford | last post: by
61 posts views Thread by Ron Ford | last post: by
reply views Thread by NPC403 | last post: by
1 post views Thread by fmendoza | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.