Thread: Q sorting a 2D array

1. Q sorting a 2D array

Hi,

I am trying to q-sort an 2D array containing 2 columns of floats. The array must be sorted on the basis of any one of the columns.

This is the code that I wrote..

Code:
```int compare( const void* a, const void* b)
{

float** p1 = (float**) a;

float** p2 = (float**) b;

if( p1[1] > p2[1])
{

return -1;
}

else if (p1[1] < p2[1])
{

return 1;
}

else
{

return 0;
}

}

int main()
{

float **array;

int i;

array = (float**)malloc(10*sizeof(float*));

for(i=0; i<10; i++)
{
array[i] = (float*)malloc(2*sizeof(float));
}

for(i=0; i<10; i++)
{

array[i][0] = i;
array[i][1] = 2*i;

}

for( i=0; i<10; i++)
{

printf("%f\t%f\n",array[i][0],array[i][1]);
}

printf("\n\n");

qsort(array, 10, sizeof(float**),compare);

for( i=0; i<10; i++)
{

printf("%f\t%f\n",array[i][0],array[i][1]);
}

return 0;

}```
As I understand it, every element in array[], is a pointer to a pointer to a float.. (float**).
So I m passing this float** to the compare function and inside the function I am asking it to look at the second element in the row pointed to by this float ** and return 1, -1 or 0.

But the output from this code is in random order and is not sorted at all. However if I run it with

Code:
``` if( p1[1] > p2[1])
{

return -1;
}

else if (p1[1] < p2[1])
{

return 1;
}

else
{

return 0;
}```
i.e. if I ask it to sort by the 1st element of each row instead of the second, the output is properly sorted.

I think the place I m going wrong is probably in the type casting inside the compare function. But I m not able to get it. Can anyone tell me what I am doing wrong..

thanks,

Avinash

2. > qsort(array, 10, sizeof(float**),compare);
You're not swapping enough memory,
2*sizeof(float) is the amount in each row of your data

3. 2*sizeof(float) is the amount in each row of your data
Yes, but the size of each element is sizeof(float*), isn't it? Since each row is a pointer to a float? Anyway, this seemed to work for me.

Here's one way to do it. No guarantees, it's been a while since I used qsort().
Code:
```#include <stdio.h>
#include <stdlib.h>

int compare( const void* a, const void* b)
{

float* p1 = *(float**) a;

float* p2 = *(float**) b;

/*printf("Compare %f %x <=> %f %x\n", p1[0], a, p2[0], b);*/

if( p1[1] > p2[1])
{

return -1;
}

else if (p1[1] < p2[1])
{

return 1;
}

else
{

return 0;
}

}

int main()
{

float **array;

int i;

array = (float**)malloc(10*sizeof(float*));

for(i=0; i<10; i++)
{
array[i] = (float*)malloc(2*sizeof(float));
/*printf("[%d] (%x)\n", i, array[i]);*/
}

for(i=0; i<10; i++)
{
/*printf("[%d][%d] (%x), [%d][%d] (%x)\n", i, 0, &array[i][0], i, 1, &array[i][1]);*/
array[i][0] = i;
array[i][1] = 2*i;

}

for( i=0; i<10; i++)
{

printf("%f\t%f\n",array[i][0],array[i][1]);
}

printf("\n\n");

qsort(array, 10, sizeof(float*),compare);

for( i=0; i<10; i++)
{

printf("%f\t%f\n",array[i][0],array[i][1]);
}

return 0;

}```

4. dwks.. U re awesome!!..
It works now.. Thanks a ton. I was quite lost back there..

So am I right in understanding that, with qsort, u should cast the variables inside the compare function into a pointer to the type that u passed in?? Is that what I missed?

thanks again..

Avi

5. Here's how it works.

You declare an array in main(). This is really a pointer to pointers to floats, but we can ignore this for now, and say that the array is of type T, with N elements. Then you call quicksort, passing it N and sizeof(T) for the second and third parameters.

Then in the compare function, you're given two void* pointers which point to elements in the array. So, you cast the pointers to (T*). But you want the values in the array, you want to compare the Ts; so you dereference this casted value, i.e.
Code:
```T one = *(T *)a;
T two = *(T *)b;

if(one < two) return -1;
if(one > two) return +1;
return 0;```
Now, it's the same thing with your code. Except that "T" is replaced with "float*", since that's the type of the elements of the array you want to sort.

Anyway, hopefully that explanation helps.