Qsort inaccuracy?

[No Such Luck]

Hi All:

The code below (using the qsort function) produces the following
incorrect result. The last two numbers are not sorted. It this
innaccurate result specific to my compiler's qsort, or is there a bug
in my code? Thanks...

Original Array:
3.125420
8.618710
4.220840
2.181950
8.852060
1.763020
0.164010

Sorted Array:
0.164010
1.763020
2.181950
3.125420
4.220840
8.852060
8.618710

------------------------------------------

#include <stdio.h>
#include <stdlib.h>

typedef int (*qsortfunc) ( const void*, const void* );


int
compare_doubles (const double *a, const double *b)
{
return (int) (*a - *b);
}

int main ()
{

int i;
double array[7];
array[0] = 3.12542;
array[1] = 8.61871;
array[2] = 4.22084;
array[3] = 2.18195;
array[4] = 8.85206;
array[5] = 1.76302;
array[6] = 0.16401;

printf ("\nOriginal Array:\n");

for (i = 0; i < 7; i++)
printf ("%lf\n", array[i]);

qsort(array, 7, sizeof(double), (qsortfunc) compare_doubles );

printf ("\nSorted Array:\n");
for (i = 0; i < 7; i++)
printf ("%lf\n", array[i]);


return 1;
}

[Lawrence Kirby]

Re: Qsort inaccuracy?

On Tue, 14 Dec 2004 08:04:10 -0800, No Such Luck wrote:
[color=blue]
> Hi All:
>
> The code below (using the qsort function) produces the following
> incorrect result. The last two numbers are not sorted. It this
> innaccurate result specific to my compiler's qsort, or is there a bug
> in my code? Thanks...
>
> Original Array:
> 3.125420
> 8.618710
> 4.220840
> 2.181950
> 8.852060
> 1.763020
> 0.164010
>
> Sorted Array:
> 0.164010
> 1.763020
> 2.181950
> 3.125420
> 4.220840
> 8.852060
> 8.618710
>
> ------------------------------------------
>
> #include <stdio.h>
> #include <stdlib.h>
>
> typedef int (*qsortfunc) ( const void*, const void* );[/color]

Get rid of that, you don't need it.
[color=blue]
> int
> compare_doubles (const double *a, const double *b)[/color]

A qsort() comparison fuction is required to have 2 parameters of type
const void *. The function you have defined here is not compatible with
this and is invalid. The fact that you had to use a cast in the call to
qsort() below should ring alarm bells. Consider that qsort() will be
passing const void * arguments to the comparison function but
const double * may not have the same representation.
[color=blue]
> {
> return (int) (*a - *b);[/color]

This is not valid. For example (int)(8.85206-8.61871) will evaluate to
zero but the numbers are not equal. Also consider what happens if the
difference is too big to fit in an int.
[color=blue]
> }[/color]

You need something like

int compare_doubles (const void *a, const void *b)
{
double da = *(const double *)a;
double db = *(const double *)b;

if (da == db)
return 0;

return (da > db) ? 1 : -1;
}

[color=blue]
> int main ()
> {
>
> int i;
> double array[7];
> array[0] = 3.12542;
> array[1] = 8.61871;
> array[2] = 4.22084;
> array[3] = 2.18195;
> array[4] = 8.85206;
> array[5] = 1.76302;
> array[6] = 0.16401;
>
> printf ("\nOriginal Array:\n");
>
> for (i = 0; i < 7; i++)
> printf ("%lf\n", array[i]);[/color]

The normal printf() conversion specifier for double is %f, C99 added
support for %lf too, but %f also works with C90 which is still in common
use.
[color=blue]
>
> qsort(array, 7, sizeof(double), (qsortfunc) compare_doubles );[/color]

qsort(array, 7, sizeof *array, compare_doubles );

You don't need the cast, and this form of the 3rd argument works even if
you changed the type of array.
[color=blue]
> printf ("\nSorted Array:\n");
> for (i = 0; i < 7; i++)
> printf ("%lf\n", array[i]);[/color]

Again %f is better.
[color=blue]
>
> return 1;
> }[/color]

Portable return values from the initial invocation of main() are 0 and
EXIT_SUCCESS which indicate success and EXUT_FAILURE which indicates
failure. The last 2 are defined in <stdlib.h>.

Lawrence

[Lawrence Kirby]

Re: Qsort inaccuracy?

On Tue, 14 Dec 2004 16:57:46 +0000, Lawrence Kirby wrote:

....
[color=blue]
> Portable return values from the initial invocation of main() are 0 and
> EXIT_SUCCESS which indicate success and EXUT_FAILURE which indicates
> failure. The last 2 are defined in <stdlib.h>.[/color]

Sorry, make that EXIT_FAILURE

Lawrence

[Al Bowers]

Re: Qsort inaccuracy?



No Such Luck wrote:[color=blue]
> Hi All:
>
> The code below (using the qsort function) produces the following
> incorrect result. The last two numbers are not sorted. It this
> innaccurate result specific to my compiler's qsort, or is there a bug
> in my code?[/color]

Yes.
The compare function is flawed. See below.
[color=blue]
> Original Array:
> 3.125420
> 8.618710
> 4.220840
> 2.181950
> 8.852060
> 1.763020
> 0.164010
>
> Sorted Array:
> 0.164010
> 1.763020
> 2.181950
> 3.125420
> 4.220840
> 8.852060
> 8.618710
>
> ------------------------------------------
>
> #include <stdio.h>
> #include <stdlib.h>
>
> typedef int (*qsortfunc) ( const void*, const void* );
>
>
> int
> compare_doubles (const double *a, const double *b)
> {
> return (int) (*a - *b);
> }[/color]

1. The return statement is wrong. For example, with
(int)(8.852060 - 8.618710), the cast to int results in a
return of 0. 0 indicates to function qsort that the two
values are equal. As you see, they are not equal.

2. The prototype for the comparison function is:
int cmp(const void *, const void *);

You need to remove the typedef.
Change the compare_doubles function to something like:

int compare_doubles (const void *v1, const void *v2)
{
const double *d1 = v1;
const double *d2 = v2;

return (*d1 < *d2)?-1:(*d1!=*d2);
}

And remove the qsortfunc cast in the qsort statement.
[color=blue]
> int main ()
> {
>
> int i;
> double array[7];
> array[0] = 3.12542;
> array[1] = 8.61871;
> array[2] = 4.22084;
> array[3] = 2.18195;
> array[4] = 8.85206;
> array[5] = 1.76302;
> array[6] = 0.16401;
>
> printf ("\nOriginal Array:\n");
>
> for (i = 0; i < 7; i++)
> printf ("%lf\n", array[i]);
>
> qsort(array, 7, sizeof(double), (qsortfunc) compare_doubles );
>
> printf ("\nSorted Array:\n");
> for (i = 0; i < 7; i++)
> printf ("%lf\n", array[i]);
>
>
> return 1;
> }
>[/color]

--
Al Bowers
Tampa, Fl USA
mailto: xabowers@myrapi dsys.com (remove the x to send email)

http://www.geocities.com/abowers822/