Problems with qsort in c

Question

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, "%2d (%+12.5le,%+12.5le)  %11.5le %11.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 :).

The parameters passed to the comparison function have type `cmplx **`, not `cmplx *`. — dbush, Jun 07 '22 at 15:59
Probably not your problem, but see [Why is `while(!feof(fp))` always wrong?](https://stackoverflow.com/questions/5431941) — Steve Summit, Jun 07 '22 at 16:01
Alternatively, keep the comparison function and replace the array of pointers to `cmplx` with an array of `cmplx`. — n. m. could be an AI, Jun 07 '22 at 16:02
As you are asking about the sorting, it would be a good idea to replace all the file related stuff by just providing a hard coded array. See [MCVE](https://stackoverflow.com/help/mcve) for more details — Gerhardh, Jun 07 '22 at 16:13
Please read the tag descriptions before attaching tags to your question. The "debugging" tag, which you attached (but I removed) states the following: "IMPORTANT NOTE: This tag is ONLY for questions about debugging techniques or the process of debugging itself, NOT for requesting help debugging your code." — Andreas Wenzel, Jun 07 '22 at 16:41
Questions seeking debugging help should generally provide a [mre] of the problem. As already pointed out by someone else, it appears that your posted code does not satisfy the requirement of being "minimal". — Andreas Wenzel, Jun 07 '22 at 16:55
Have you tried running your code line by line in a debugger while monitoring the values of all variables, in order to determine in which line your program stops behaving as intended? If you did not try this, then you may want to read this: [What is a debugger and how can it help me diagnose problems?](https://stackoverflow.com/q/25385173/12149471) You may also want to read this: [How to debug small programs?](https://ericlippert.com/2014/03/05/how-to-debug-small-programs/) — Andreas Wenzel, Jun 07 '22 at 16:59
Even if using a debugger does not actually solve the problem, it should at least help you to isolate the problem and to create a [mre] of the problem, so that it will be easier for other people to help you. Most people will not be willing to debug your whole program for you, [as that should be your job](https://idownvotedbecau.se/nodebugging/). — Andreas Wenzel, Jun 07 '22 at 17:00
In your case, it would probably be helpful to set a debugger breakpoint at the start of the function `comparador` and run that function line by line while monitoring the values of all variables, to see if the behavior of that function is correct. — Andreas Wenzel, Jun 07 '22 at 17:04
Aside: Alternative to `c->r = sqrt(c->x*c->x + c->y*c->y);` --> `c->r = hypot(c->x, c->y);`. — chux - Reinstate Monica, Jun 07 '22 at 20:02

score 3 · Accepted Answer · answered Jun 07 '22 at 16:54

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;

chux - Reinstate Monica · Answer 2 · 2022-06-07T17:19:11.380

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 qsort they 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) {

Problems with qsort in c

2 Answers2