Qsort isn't working properly for me:
It should order, in ascending order, the third column and, if equal, comparing the fourth one. However this isn't the result I'm getting.
Expected result:
8 ( 6.91200e-01, 4.44400e-01) 8.21735e-01 5.71396e-01
5 ( 7.07107e-01, 7.07107e-01) 1.00000e 00 7.85398e-01
4 ( 0.00000e 00, 1.00000e 00) 1.00000e 00 1.57080e 00
6 (-7.07107e-01,-7.07107e-01) 1.00000e 00 3.92699e 00
11 ( 1.06955e 00, 2.12748e-01) 1.09051e 00 1.96350e-01
12 (-2.12748e-01, 1.06955e 00) 1.09051e 00 1.76715e 00
13 (-1.06955e 00,-2.12748e-01) 1.09051e 00 3.33794e 00
14 ( 2.12748e-01,-1.06955e 00) 1.09051e 00 4.90874e 00
16 ( 7.93701e-01, 7.93701e-01) 1.12246e 00 7.85398e-01
17 (-1.08422e 00, 2.90515e-01) 1.12246e 00 2.87979e 00
18 ( 2.90515e-01,-1.08422e 00) 1.12246e 00 4.97419e 00
1 ( 1.25992e 00, 0.00000e 00) 1.25992e 00 0.00000e 00
2 (-6.29961e-01, 1.09112e 00) 1.25992e 00 2.09440e 00
3 (-6.29961e-01,-1.09112e 00) 1.25992e 00 4.18879e 00
10 ( 1.00000e 00, 1.00000e 00) 1.41421e 00 7.85398e-01
15 (-1.00000e 00, 1.00000e 00) 1.41421e 00 2.35619e 00
7 ( 1.00000e 00,-1.00000e 00) 1.41421e 00 5.49779e 00
0 ( 2.00000e 00, 0.00000e 00) 2.00000e 00 0.00000e 00
9 (-1.31626e 00,-2.04725e 00) 2.43387e 00 4.14099e 00
Actual result:
0 ( 2.00000e 00, 0.00000e 00) 2.00000e 00 0.00000e 00
17 (-1.08422e 00, 2.90515e-01) 1.12246e 00 2.87979e 00
16 ( 7.93701e-01, 7.93701e-01) 1.12246e 00 7.85398e-01
15 (-1.00000e 00, 1.00000e 00) 1.41421e 00 2.35619e 00
14 ( 2.12748e-01,-1.06955e 00) 1.09051e 00 4.90874e 00
13 (-1.06955e 00,-2.12748e-01) 1.09051e 00 3.33794e 00
12 (-2.12748e-01, 1.06955e 00) 1.09051e 00 1.76715e 00
11 ( 1.06955e 00, 2.12748e-01) 1.09051e 00 1.96350e-01
10 ( 1.00000e 00, 1.00000e 00) 1.41421e 00 7.85398e-01
9 (-1.31626e 00,-2.04725e 00) 2.43387e 00 4.14099e 00
8 ( 6.91200e-01, 4.44400e-01) 8.21735e-01 5.71396e-01
7 ( 1.00000e 00,-1.00000e 00) 1.41421e 00 5.49779e 00
6 (-7.07107e-01,-7.07107e-01) 1.00000e 00 3.92699e 00
5 ( 7.07107e-01, 7.07107e-01) 1.00000e 00 7.85398e-01
4 ( 0.00000e 00, 1.00000e 00) 1.00000e 00 1.57080e 00
3 (-6.29961e-01,-1.09112e 00) 1.25992e 00 4.18879e 00
2 (-6.29961e-01, 1.09112e 00) 1.25992e 00 2.09440e 00
1 ( 1.25992e 00, 0.00000e 00) 1.25992e 00 0.00000e 00
18 ( 2.90515e-01,-1.08422e 00) 1.12246e 00 4.97419e 00
I have no compilation errors or runtime errors. However, when executing it with valgrind there are some errors saying that the in comparator function (comparador), value of size 8 can't be read. However I can't manage to find the problem.
I think the error should be here:
qsort(mat, n, sizeof(cmplx *), &comparador);
int comparador(const void * a, const void * b){
cmplx *c = (cmplx *)a;
cmplx *d = (cmplx *)b;
if(fabs(c->r - d->r) < TOL){
if(fabs(c->arg - d->arg) < TOL){
return 0;
}else{
return c->arg > d->arg ? 1 : -1;
}
}else{
return c->r > d->r ? 1 : -1;
}
}
If you want to try the code by yourself, here is the full code. It works by entering the name of your file you gave the data in and then the name of the resultant file.
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#define TOL 1e-8
typedef struct comp {
int index ;
double x ,y; /* cartesianes */
double r , arg ; /* polars */
struct comp * seg ;
} cmplx ;
cmplx prod ( cmplx , cmplx );
int quocient ( cmplx , cmplx , cmplx *);
cmplx ** nroot ( cmplx , int);
void polar ( cmplx *);
void cartesia ( cmplx *);
void escriuCmplx ( FILE *f , cmplx );
cmplx * afegir ( cmplx * primer , cmplx *z );
void alliberar ( cmplx * primer );
int comparador(const void *, const void *);
int main(void){
FILE * fitxer;
char nomFitxer[20];
cmplx *primer, *z, *aux, w0, **mat;
int n, i;
w0.x = 0.1234;
w0.y = 0.5678;
polar(&w0);
primer = NULL;
scanf("%s", nomFitxer);
fitxer = fopen(nomFitxer, "r");
if(fitxer == NULL){
printf("El fitxer no existeix\n");
return 1;
}
while(!feof(fitxer)){ /*Mentre no arribem al final del document*/
z = (cmplx *)malloc(sizeof(cmplx));
if(z == NULL){
printf("Error: malloc ha retornat NULL\n");
exit(1);
}
/*S'ha de reservar memòria per z ja que
per cada iteració voem una adreça distinta*/
fscanf(fitxer, "%le %le %d", &z->x, &z->y, &n);
if((fabs(z->x) < TOL && fabs(z->y) < TOL) || n < 1){
free(z);
continue; /*Alliberam adreça i saltam tot el codi vinent*/
}
polar(z); /*Formatam z*/
primer = afegir(primer, z); /*Afegim z*/
if(n == 1){
aux = (cmplx *)malloc(sizeof(cmplx));
if(aux == NULL){
printf("Error: malloc ha retornat NULL\n");
exit(1);
}
*aux = prod(*z, w0);
primer = afegir(primer, aux);
aux = (cmplx *)malloc(sizeof(cmplx));
if(aux == NULL){
printf("Error: malloc ha retornat NULL\n");
exit(1);
}
if(quocient(*z, w0, aux)){
primer = afegir(primer, aux);
}
}else if(n > 1){
mat = nroot(*z, n);
for(i = 0; i < n; i ){
primer = afegir(primer, mat[i]);
}
free(mat); /*Basta fer free de la matriu, els elements ja s'alliberaran amb la llista apuntada*/
}
}
fclose(fitxer);
if(primer == NULL){
printf("El fitxer és buid\n");
return 1;
}
n = primer->index 1;
mat = (cmplx **)malloc(n*sizeof(cmplx *));
if( mat == NULL){
printf("Error: malloc ha retornat NULL\n");
exit(1);
}
aux = primer;
for(i = 0; i < n; i ){
mat[i] = aux;
aux = aux->seg;
}
/*Fins aquí tot bé crec, supòs, esper, res. (m'ho ha dit valgrind)*/
qsort(mat, n, sizeof(cmplx *), &comparador); /*Aquí problema*/
scanf("%s", nomFitxer);
fitxer = fopen(nomFitxer, "w");
if(fitxer == NULL){
printf("Error: error en el fitxer de sortida\n");
exit(1);
}
for(i = 0; i < n; i ){
escriuCmplx(fitxer, *mat[i]);
}
fclose(fitxer);
free(mat);
alliberar(primer);
return 0;
}
/*Funcions de càlcul*/
cmplx prod( cmplx a, cmplx b){
cmplx c;
double arg;
c.r = a.r*b.r;
if(fabs(c.r) < TOL){ /*Cas r = 0*/
c.r = 0;
c.arg = 0;
}else{
arg = a.arg b.arg; /*Si a i b estan ben formatats, arg està en [0, 4PI)*/
c.arg = arg >= 2*M_PI ? arg - 2*M_PI : arg;
}
cartesia(&c);
return c;
}
int quocient( cmplx a, cmplx b, cmplx *c){
double arg;
if((b.r) < TOL) return 0;
c->r = a.r/b.r;
if(fabs(c->r) < TOL){ /*Cas r = 0*/
c->r = 0;
c->arg = 0;
}else{
arg = a.arg - b.arg; /*Si a i b estan ben formatats, arg està en (-2PI, 2PI)*/
c->arg = arg < 0 ? arg 2*M_PI : arg;
}
cartesia(c);
return 1;
}
cmplx ** nroot( cmplx c, int n){
cmplx ** mat;
int k;
double r_n, arg;
if(fabs(c.r) < TOL){ /*Cas r = 0*/
r_n = 0;
}else{
r_n = pow(c.r, 1.0/n);
}
mat = (cmplx **)malloc(n*sizeof(cmplx *));
if( mat == NULL){
printf("Error: malloc ha retornat NULL\n");
exit(1);
}
for(k = 0; k < n; k ){
mat[k] = (cmplx *)malloc(sizeof(cmplx));
if( mat[k] == NULL){
printf("Error: malloc ha retornat NULL\n");
exit(1);
}
mat[k]->r = r_n;
if(r_n == 0){ /*Cas r = 0*/
mat[k]->arg = 0;
}else{
arg = (c.arg 2*M_PI*k)/n; /*Si c.arg està ben formatat, m[k]->arg està en [0, 4PI)*/
mat[k]->arg = arg >= 2*M_PI ? arg - 2*M_PI : arg;
}
cartesia(mat[k]);
}
return mat;
}
/*Funcions bàsiques*/
void polar( cmplx * c){
double arg = atan2(c->y, c->x);
c->arg = arg < 0 ? arg 2*M_PI : arg; /*Si arg és menor a 0, sumam 2PI*/
c->r = sqrt(c->x*c->x c->y*c->y); /*r és el mòdul del complex*/
}
void cartesia( cmplx * c){
c->x = c->r*cos(c->arg);
c->y = c->r*sin(c->arg);
}
void escriuCmplx ( FILE *f , cmplx c ){
fprintf(f, "- (% 12.5le,% 12.5le) .5le .5le\n", c.index, c.x, c.y, c.r, c.arg);
}
/*Funcions per llista*/
cmplx * afegir ( cmplx *primer , cmplx *z ){
z->seg = primer;
if(primer == NULL){
z->index = 0;
}else{
z->index = primer->index 1;
}
return z;
}
void alliberar (cmplx *primer){
if(primer != NULL){
alliberar(primer->seg);
free(primer);
}
}
int comparador(const void * a, const void * b){
cmplx *c = (cmplx *)a;
cmplx *d = (cmplx *)b;
if(fabs(c->r - d->r) < TOL){
if(fabs(c->arg - d->arg) < TOL){
return 0;
}else{
return c->arg > d->arg ? 1 : -1;
}
}else{
return c->r > d->r ? 1 : -1;
}
}
If you want to compare the results with some set expected ones try entering a file with this data:
2. 0. 3
0. 1. 2
1. -1. 1
0. 0. 0
1. 1. -2
1. 1. 4
-1. 1. 3
You may also have to #define M_PI 3.14159265358979323846
Any coments or suggestions are welcome :).
CodePudding user response：
The arguments to the comparator function are pointers to elements of the array. Since those elements are themselves pointers, you need to use pointers to pointers:
int comparador(const void * a, const void * b){
cmplx *c = *(cmplx **)a;
cmplx *d = *(cmplx **)b;
CodePudding user response：
In addition to using the correct access Chris Dodd, comparador() with its < TOL fails to do a proper compare.
Consider comparador(a,b) returns 0 because a,b are close. Same for comparador(b,c), but comparador(a,c) returns non-zero. This violates consistency for comparing.
When the same objects (consisting of size bytes, irrespective of their current positions in the array) are passed more than once to the comparison function, the results shall be consistent with one another. That is, for
qsortthey shall define a total ordering on the array, ...
C17dr § 7.22.5 4
Sorting a 2D data into a linear 1D with tolerance will lead to undefined behavior (UB). I recommend to sort without TOL.
Suggest:
int comparador(const void * a, const void * b){
const cmplx *c = *(const cmplx **)a;
const cmplx *d = *(const cmplx **)b;
if(fabs(c->r - d->r) == 0) {
return (c->arg > d->arg) - (c->arg < d->arg);
}
return c->r > d->r ? 1 : -1;
}
Or
// if(fabs(c->r - d->r) == 0) {
if(c->r == d->r) {