# How to use qsort function of C library ?

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

1. ### peregesGuest

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

Is qsort the best sorting algorithm out there ?

pereges, Apr 8, 2008

2. ### peregesGuest

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

3. ### Walter RobersonGuest

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

>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
4. ### Keith ThompsonGuest

pereges <> writes:
> It is not explained well in my manual. can someone please tell me
>
> 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
5. ### Keith ThompsonGuest

pereges <> writes:
> It is not explained well in my manual. can someone please tell me
>
> 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
6. ### WillemGuest

Walter wrote:
) In article <>,
) pereges <> wrote:
)>It is not explained well in my manual. can someone please tell me
)
)>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
7. ### Chris McDonaldGuest

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

>'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
8. ### peregesGuest

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
9. ### Ben BacarisseGuest

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
10. ### peregesGuest

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

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.

--

12. ### peregesGuest

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"

typedef struct bounding_sphere_struct
{
vector cen; /*center of bounding sphere */
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->maxspheres = o->ntri;
for(i=0; i<o->ntri; i++)
{
>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);
}
/*printf("Flag:%d Center:%f %f %f radius: %f\n",flag, kdroot-
[i][i]
}
build_kdtree(kdroot, 0);
return kdroot;

}[/i][/i][/i]

pereges, Apr 9, 2008
13. ### peregesGuest

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"

typedef struct bounding_sphere_struct
{
vector cen; /*center of bounding sphere */
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->maxspheres = o->ntri;
for(i=0; i<o->ntri; i++)
{
>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);
}
/*printf("Flag:%d Center:%f %f %f radius: %f\n",flag,
}

build_kdtree(kdroot, 0);
return kdroot;

}[/i][/i][/i]

pereges, Apr 9, 2008
14. ### peregesGuest

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

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

pereges, Apr 9, 2008
15. ### Walter RobersonGuest

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
16. ### Keith ThompsonGuest

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);
> }
>
> ..................
> ..................
>

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
17. ### peregesGuest

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
18. ### Barry SchwarzGuest

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