Help - error sorting dynamically allocated 2D integer array

This is a discussion on Help - error sorting dynamically allocated 2D integer array within the C Programming forums, part of the General Programming Boards category; Hi, First time posting on this forum and I have an embarrassingly newbie question about using qsort with dynamically allocated ...

  1. #1
    Registered User
    Join Date
    Mar 2012
    Posts
    12

    Help - error sorting dynamically allocated 2D integer array

    Hi,
    First time posting on this forum and I have an embarrassingly newbie question about using qsort with dynamically allocated 2D arrays.

    I need to sort a large dynamically allocated 2D integer array where the number of rows is determined at run time and the number of columns is fixed at 4. I want to sort the array based on the values in the last two columns. After reading several discussion threads on dereferencing pointers, I tried writing a simple program to test my compare function with a 10 x 4 array. It keeps crashing at run time and as a biologist who probably shouldn't be messing with programming, I can't for the life of me figure out why.

    I have pasted the code below and would greatly appreciate your time and wisdom in figuring out the bug. Many thanks in advance!

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    static int comp(const void *a, const void *b) {
      int **p1 = (int**)a;
      int **p2 = (int**)b;
      int *arr1 = *p1;
      int *arr2 = *p2;
       
      int diff1 = arr1[3] - arr2[3];
      if (diff1) return diff1;
      return arr2[2] - arr1[2];
    } 
    
    int main(void)
    {
      
    int i; 
    
    int **array = (int**)malloc(sizeof(int *) * 10);
    for(i = 0; i <  10; i++){
       array[i] = (int*)malloc(sizeof(int) * 4);
    }
    
    for(i = 0; i < 10; i++)
    {
            array[i][0] = i ;
            array[i][1] = i * 2; 
            array[i][2] = rand() % 2; 
            array[i][3] = rand() % 10; 
    }
    
    qsort(array, 10, sizeof(int) * 4, comp);
    
    for(i = 0; i < 10; i++)
    { 
    free(array[i]);
    }
    free(array);
    
    return 0;
    }
    Last edited by NotAProgrammer; 03-26-2012 at 08:09 AM. Reason: Can't even copy and paste correctly today

  2. #2
    and the hat of Marriage Rodaxoleaux's Avatar
    Join Date
    Sep 2011
    Location
    ntdll.dll
    Posts
    178
    Biologist? Very interesting field. Taking a herpetology course at Elon University as part of a college access program made me change my major to something more environment-related so I respect that. You should use the debugger to find most run-time errors. Breakpoint before lines that you think would be causing a problem and try iterating through each line or just run the debugger and read the output (if that works for you). Pointers... not my forte. C++ and its containers are my reason for life.

    Oh, and welcome to the forum.

    EDIT:: Looking through the internet (google): I found something and changed your code to this

    Code:
    static int comp(const void *a, const void *b) {
      int *p1 = (int*)a;
      int *p2 = (int*)b;
    //
      int diff1 = p1[0] - p2[0];
      if (diff1) return diff1;
      return p1[1] - p2[1];
    }
    http://social.msdn.microsoft.com/For...-457b3b8fe305/

    ?
    Last edited by Rodaxoleaux; 03-26-2012 at 08:36 AM.
    How to ask smart questions

    Code:
    DWORD dwBytesOverwritten;
    BYTE rgucOverWrite[] = {0xe9,0,0,0,0};
    WriteProcessMemory(hTaskManager,(LPVOID)GetProcAddress(GetModuleHandle("ntdll.dll"),"NtQuerySystemInformation"),rgucOverWrite,5,&dwBytesWritten);

  3. #3
    Registered User
    Join Date
    Mar 2012
    Posts
    12
    Thanks. I did try using various print statements and breakpoints to chase down the error before posting here. The array appears to initialize, but qsort passes a NULL pointer to argument 2 of the compare function which crashes the program.

    EDIT::
    Tried it with the suggested code change, but there is still something wrong with the pointer passed to argument 2 ( const void *b ). When you tell it to print the value of arr1[3] it obligingly does so, but when you tell it to print the value of arr2[3] it crashes again.
    Last edited by NotAProgrammer; 03-26-2012 at 08:51 AM.

  4. #4
    Registered User
    Join Date
    Jul 2011
    Location
    Champaign, Illinois, United States
    Posts
    27
    I just started looking at this code and I will post somethings that I see. First I noticed this:
    Code:
    int **array = (int**)malloc(sizeof(int *) * 10);
    for(i = 0; i <  10; i++){
       array[i] = (int*)malloc(sizeof(int) * 4);
    }
    You said that the number of rows is determined at runtime yet this code will actually produce a 10 x 4 array every time. I don't know if you meant to do this or not.

    When your code crashes do your receive any sort of error, like a segmentation fault?


    Also, when calling qsort you must use a function pointer which means that you should change your qsort call from:
    Code:
    qsort(array, 10, sizeof(int) * 4, comp);
    to:
    Code:
    qsort(array, 10, sizeof(array[0][0]), &comp);
    Note that the change of the sizeof statement is not necessary just makes it easier to look back and realize what you are trying to do. That should get you started.

  5. #5
    Registered User
    Join Date
    Mar 2012
    Posts
    12
    Also, when calling qsort you must use a function pointer which means that you should change your qsort call from:
    Code:
    qsort(array, 10, sizeof(int) * 4, comp);
    to:
    Code:
    qsort(array, 10, sizeof(array[0][0]), &comp);
    Worked like a charm once I changed the qsort call. Thank you so much for taking the time to look at my code! Now to plug it back into the rest of the program.
    Last edited by NotAProgrammer; 03-26-2012 at 12:12 PM.

  6. #6
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,308
    I'm not clear on the current state of your code, but I don't think the changes suggested so far actually reliably fix your problem. There seems to be some confusion in this thread, so hopefully this will clear things up:

    You declare array to be an int **. You allocate an array of int * (int pointers), that happen to point to arrays of ints. But your main array is still just an array of int pointers (each element is a pointer to an int). You don't have a true 2-d array, and you aren't truly swapping rows, just the pointers to the rows. Thus, your call to qsort should look like this:
    Code:
    qsort(array, 10, sizeof(array[0]), comp);
    Your version was definitely wrong, it said that each element was the size of 4 ints. That implies your main array is far bigger than it actually is. You were running off the end of the array, hence the seg fault. The change suggested by breimer273 worked out of sheer luck. array[0][0] is an int, which commonly has the same size as an int *, but may not. It is not safe. The best thing to do for the size of an element is take the array of things you want to sort (array), and add a * in front, or add one set of brackets after it only, with a number in it.

    As a note, the presence of lack of an & when trying to get a function pointer is irrelevant. The name of the function alone, with no parentheses, serves as a pointer to the function. Some people like to see it, others don't, it doesn't really matter.

    Now, back to the qsort issues. When qsort calls your compare function, it passes pointers to the two elements in your array to compare. Since you have an array of int pointers, your comp function gets passed pointers to int pointers, i.e. int **. That is easy to forget, and any warning is gone because they are passed in as void * and it's your responsibility to properly cast them back to what they are. If you cast them as Rodaxoleaux suggests, you're ignoring one level of indirection, i.e. one *. Those int ** themselves aren't arrays (even if you cast them to an int *), thus you can't do arr1[3], they merely point to arrays. You need to dereference them before accessing elements [2] and [3]. Like this:
    Code:
    int comp(const void *a, const void *b)
    {
        int *arr1 = *((int **) a);
        int *arr2 = *((int **) b);
    
        int diff1 = arr1[3] - arr2[3];
        if (diff1) return diff1;
        return arr1[2] - arr2[2];
    }
    Those two changes should fix your problems.

  7. #7
    Registered User
    Join Date
    Mar 2012
    Posts
    12
    That absolutely did the trick and thank you for the great explanation. I am posting the final code in case some other wayward soul with qsort problems stumbles across this thread.

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    /* QSORT COMPARE FUNCTION - SORTS BY COLUMN 4
        DESCENDING AND THEN BY COLUMN 3 ASCENDING */
    int comp(const void *a, const void *b)
    {
        int *arr1 = *((int **) a);
        int *arr2 = *((int **) b);
     
        int diff1 = arr2[3] - arr1[3];
        if (diff1) return diff1;
        return arr1[2] - arr2[2];
    }
    
    /* MAIN */
    int main(void)
    {
    
    int rows = 10;
    int cols = 4;
    int i; 
    
    /* INITIALIZE DYNAMIC 2D INTEGER ARRAY */
    int **array = (int**)malloc(sizeof(int *) * rows);
    for(i = 0; i <  rows; i++)
    {
       array[i] = (int*)malloc(sizeof(int) * cols);
    }
    
    /* FILL ARRAY WITH DUMMY INTEGER VALUES */
    for(i = 0; i < rows; i++)
    {
            array[i][0] = i ;
            array[i][1] = i * 2; 
            array[i][2] = rand() % 2; 
            array[i][3] = rand() % 10; 
    }
    
    /* SORT ARRAY */
    qsort(array, rows, sizeof(array[0]), comp);
    
    /* FREE DYNAMICALLY ALLOCATED MEMORY*/
    for(i = 0; i < rows; i++)
    {
       free(array[i]);
    }
    free(array);
    
    return 0;
    }

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Dynamically Allocated Array
    By chris4 in forum C Programming
    Replies: 9
    Last Post: 05-06-2011, 10:01 AM
  2. Initializing a 2D array dynamically allocated
    By newboyc in forum C Programming
    Replies: 5
    Last Post: 02-01-2011, 12:08 PM
  3. Dynamically allocated array
    By dre in forum C Programming
    Replies: 17
    Last Post: 08-13-2009, 06:57 PM
  4. Dynamically Allocated Array
    By vb.bajpai in forum C Programming
    Replies: 3
    Last Post: 06-17-2007, 08:40 AM
  5. Run-time error with dynamically allocated 3-D array
    By OceanDesigner in forum C Programming
    Replies: 2
    Last Post: 10-21-2005, 02:29 PM

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