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

When you change all the indexing back to 0-based, what result are you getting? — Oliver Charlesworth
– Oliver Charlesworth, Commented Sep 12, 2013 at 21:50
you may wish to store the matrix in the column-major order and then call sort on each colum (which then would be in a consecutive chunk of memory) — jev
– jev, Commented Sep 13, 2013 at 9:09
@OliCharlesworth colnum=0 gives me junk. That is what is puzzling to me. Where did the +1 offset arise from ? — GreenEye
– GreenEye, Commented Sep 13, 2013 at 13:29

jxh · Accepted Answer · 2013-09-13 00:26:00Z

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; /*...*/

edited Sep 13, 2013 at 0:26

answered Sep 13, 2013 at 0:14

jxh

70.8k8 gold badges116 silver badges204 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

GreenEye Over a year ago

I think I understand all of what you are saying. But, since I am initializing my array columns as 0 and 1, why would setting colnum=1 sort my array by column 1, colnum=2 sort by column 2, and setting colnum=0 give me junk ? What is puzzling to me is where the +1 offset comes from in my code ?

jxh Over a year ago

Your program is not initializing your array at columns 0 and 1.

GreenEye Over a year ago

I got it now. I had changed the indices for some testing, and then did not change it back. Now it behaves properly. Thanks.

Collectives™ on Stack Overflow

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

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related