Q sorting a 2D array

[avi2886]

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..

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

 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

[Salem]

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

[dwks]

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().

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

}

[avi2886]

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

[dwks]

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.

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.