qsort in C based on a column in 2d array: unexpected behavior

Question

I am trying to sort a 2d array based on a particular column using qsort in C. I am attaching a minimal working code I am using. Essentially I am passing the pointer to the rows of the array to qsort, and based on the column number I want to sort, I modify the element to compare inside the compare function. Now, according to C convention, if I have 2 columns, I expect colnum=0 and colnum=1 to correspond to columns 1 and 2. But, in my implementation, I get the correct result if colnum=1 means column 1 and colnum=2 means column 2. I am stumped as to why this should be ? (I have also included the array allocation function I use).

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include "myfun.h"

static int colnum = 0;

int cmp(const void * a,const void * b);

int main(){

int i;
double **z1;

z1=matrix(5,2);
for (i=0; i<5; i++){
    z1[i][1]=-i-1; z1[i][2]=16*i+10; 
    printf("before sort z1 %lf %lf \n",z1[i][1],z1[i][2]);
}

colnum=2;
qsort(z1,5,sizeof(double*),cmp);

for (i=0; i<5; i++){
    printf("after sort z1 %lf %lf \n",z1[i][1],z1[i][2]);
}

getchar();
}

int cmp(const void * a,const void * b)
{
double** x = (double**) a;
double** y = (double**) b;

double xval, yval;

xval = *(*(x)+colnum);
yval = *(*(y)+colnum);

printf("%lf %lf \n",xval,yval);

if (xval < yval )
{
    return 1;
}
else if (xval > yval)
{
    return -1;
}
else
{
    return 0;
}
}

double** matrix(int rows,int cols){
int k;
double **m;
m = (double **)malloc(rows * sizeof(double *));
for (k=0; k<rows; k++){
    m[k] = (double *)malloc(cols * sizeof(double));
}
return m;
}

Answer 1

Your program has undefined behavior, because your are accessing memory beyond the boundary allocated by your inner allocation loop of matrix():

    m = (double **) malloc(rows * sizeof(double *));
    for (k = 0; k < rows; k++) {
        m[k] = (double *) malloc(cols * sizeof(double));
    }

Since cols has the value 2, malloc() only returns memory for 2 elements of type double. But, your code is initializing and reading a non-existing third element instead.

Since doing so is undefined, producing the output you expect is within the realm of possible behaviors. However, it is incorrect since you run the risk of corrupting the heap, and reading invalid data. Running your program under valgrind produces "Invalid write" and many "Invalid read" errors due to this problem in your program.

The correct approach is to store the values in their proper 0 and 1 column indexes in your initialization, set colnum to 1 to sort by the second column, and read from the proper 0 and 1 indexes when you print the array values.

    z1 = matrix(5, 2);
    for (i = 0; i < 5; i++) {
        z1[i][0] = -i - 1;
        z1[i][1] = 16 * i + 10;
        printf("before sort z1 %lf %lf \n", z1[i][0], z1[i][1]);
    }

    colnum = 1;
    qsort(z1, 5, sizeof(double *), cmp);

    for (i = 0; i < 5; i++) {
        printf("after sort z1 %lf %lf \n", z1[i][0], z1[i][1]);
    }

As a side note, when I was formatting your code for this answer, I noticed that you used an old C anachronism, probably unintentionally:

    z1[i][1]=-i-1; /*...*/

The =- construct was the original C's (pre C.89) way of spelling the -= operator. It is highly unlikely you will end up using a compiler that will honor that operator without a diagnostic, but you should be wary of this syntax, and separate the = and the - tokens to remove the ambiguity.

    z1[i][1] = -i - 1; /*...*/