1

I'm trying to sort a 2d array of pointers using qsort. The only issue I have right now is originally I was using statically declared arrays now switching over to pointers. I'm almost tempted to switch to structs but being stubborn that I can't get this to work.

So far I malloc the 2d array of pointers[array2d[m][3] was the intended size]:

     int **array2d;

     array2d = (int**)malloc((m)*sizeof(int*));

     for(i=0; i<=m; i++)
       array2d = [i]=(int*)malloc(3*sizeof(int));
     qsort(array2d, m, 3*sizeof(int**),comp);

My compare is:

int comp(const void* left, const void*right)                                                                                  
{

  const int *a = *(const int**)left;
  const int *b = *(const int**)right;

  return a-b;
}

Although I'm not sure how to structure the compare to work with 2d pointers.

4
  • Your comp function is wrong. What if a is the minimum possible integer value and b is 1? Then a - b will be the maximum possible integer value (on most systems) because of wraparound in integer operations, which is positive even though the result of comp should be negative. Commented Mar 12, 2012 at 19:19
  • Are the three ints a single big value? (i.e. if int was 32bit, is it a 96bit number) Commented Mar 12, 2012 at 19:22
  • The 3 originally signified the 3 spaces inside the 2nd dimension, like at row 1 there are 3 values. Commented Mar 12, 2012 at 19:26
  • @AdamMihalcin Yea now that I look at it I should prob put 2 case to catch that, it worked originally for the other program I had so I didn't tamper with it. Commented Mar 12, 2012 at 19:28

1 Answer 1

1

From the code snippet you provided I am assuming you were trying to sort each row of the matrix separately. The first thing I noticed is that there is a typo in the memory allocation of columns (2nd index) of the matrix.

Correct memory allocation of a numRow x numColumns matrix would be as follows:

/* loop counter */
int i;

/* dynamic array sizes */
const int numRow = 5;
const int numColumns = 25;

/* allocate the row pointers */
int **dynamic2d = (int **)malloc(numRow * sizeof(int *));

/* for each row pointer */
for(i = 0; i < numRow; i++)
{
    /* allocate columns */
    dynamic2d[i] = (int *)malloc(numColumns * sizeof(int));
}

Next you won't be able to simply call the qsort(..) method only once. That method expects a "flat" or one-dimensional array. You will need to call the qsort(...) method separately for each row of the matrix. This is demonstrated below:

/* sort array */
for(i = 0; i < numRow; i++)
    qsort(dynamic2d[i], numElements, sizeof(int *), comp);

Lastly, you made a mistake with your comparator method. This method has strict rules that need to be followed in order to work correctly. Current specifications say, "The application shall ensure that the function returns an integer less than, equal to, or greater than 0, if the first argument is considered respectively less than, equal to, or greater than the second. If two members compare as equal, their order in the sorted array is unspecified."

This is a simple fix. Simply write the logic to produce those results as seen below:

int comp(const void* firstArg, const void* secondArg)
{
   /* get the values of the arguments */
   int first = *(int *)firstArg;
   int second = *(int *)secondArg;

   /* return the value as expected by the qsort() method */
   if(first < second)
   {
      return 1;
   }
   else if(second < first)
   { 
     return -1;
   }

   return 0;
}

Last thing to note, this will sort greatest to least. Do not switch the logic around in the comparator if you want least to greatest. The sort will not return accurate results. The correct way to do this is by reading the array from back to front as seen below: You can swap the arguments in the comparator to change the sorting order or read the results from back to front.

int comp(const void* firstArg, const void* secondArg)
{
    /* get the values of the arguments */
    int first = *(int *)secondArg;
    int second = *(int *)firstArg;
    ...
}

or

/* print greatest to smallest */
for(i = 0; i < numRow; i++)
{
    /* start at front and work to back */
    for(j = 0; j < numColumns; j++)
        printf("%d ", dynamic2d[i][j]);
    printf("\n");
}

/* print smallest to greatest */
for(i = 0; i < numRow; i++)
{
    /* start at back and work to front */
    for(j = numColumns- 1; j >= 0; j--)
        printf("%d ", dynamic2d[i][j]);
    printf("\n");
}

Hopefully this helps! If you need to sort the entire matrix as a whole... that is a different beast all together.

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

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.