Q sorting a 2D array

This is a discussion on Q sorting a 2D array within the C Programming forums, part of the General Programming Boards category; Hi, I am trying to q-sort an 2D array containing 2 columns of floats. The array must be sorted on ...

  1. #1
    Registered User
    Join Date
    Feb 2009
    Posts
    26

    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. #2
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,442
    > qsort(array, 10, sizeof(float**),compare);
    You're not swapping enough memory,
    2*sizeof(float) is the amount in each row of your data
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  3. #3
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,046
    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;
    
    }
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  4. #4
    Registered User
    Join Date
    Feb 2009
    Posts
    26
    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. #5
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,046
    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.
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. malloced 2d array passed to qsort
    By jamie85 in forum C Programming
    Replies: 7
    Last Post: 11-25-2005, 12:55 PM
  2. Copying from one 2d array to another....with a twist
    By Zildjian in forum C++ Programming
    Replies: 2
    Last Post: 10-24-2004, 07:39 PM
  3. 2D array sorting from min. to max.
    By khaled_helmy in forum C Programming
    Replies: 1
    Last Post: 10-14-2004, 02:17 PM
  4. Unknown Memory Leak in Init() Function
    By CodeHacker in forum Windows Programming
    Replies: 3
    Last Post: 07-09-2004, 09:54 AM
  5. Quick question about SIGSEGV
    By Cikotic in forum C Programming
    Replies: 30
    Last Post: 07-01-2004, 07:48 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21