sorting a two-dimensional array using qsort

Hyuga · #1 04-Aug-2005, 02:40

Hello again

I'm trying to sort a 2D array using qsort, but I'm not sure how can I use qsort with this kind of arrays.

First of all, my array is declared as a char **array. I have as many rows as, let's say, numLines, and in every position I have a string of 3 chars.

CPP / C++ / C Code:

char **array;
int numLines = 3;
int indexArray;

array = malloc((numLines-1) * sizeof(*array));
if(array != NULL) {
   for (indexArray = 0;indexArray < numLines; indexArray++)
      array[indexArray] = malloc(3 + 1);  /* +1 for /0 char*/

   /*assign random values for testing*/
   array[0]="027";
   array[1]="023";
   array[2]="012";
}

Now, I want to sort the values of the array as if they where integers. I have declared a comparison function like that:

CPP / C++ / C Code:

int Compare (const void *a, const void *b){
   int da = atoi(a);
   int db = atoi(b);

   return (da > db) - (da < db);
}

And when I want to sort the array, I call the qsort function like that:

CPP / C++ / C Code:

qsort(&array[0], numLines, (3 + 1), &Compare);

I don't know how many mistakes I've done in all these steps.
Maybe my comparing function is not correct? I've tested with two individual members of the array and it returned the correct values.
Maybe the call to qsort is absolutly incorrect? I think that this is the cause of my problems, but don't know how to solve it.

Thanks in advance for your help and patience.

maprich · #2 04-Aug-2005, 06:06

qsort is usually used to sort 1D arrays, but I think sorting 2D arrays can be done as well.

Quote:

Originally Posted by Hyuga

CPP / C++ / C Code:

array = malloc((numLines-1) * sizeof(*array));

In above the (numLines-1) is incorrect. It should be just:

CPP / C++ / C Code:

array = malloc( numLines*sizeof(*array) );

Your comparing function has a big confusion in the "return ..." line. However the whole thing should be modified because we are quick-sorting 2D arrays instead of 1D. So I suggest the following:

CPP / C++ / C Code:

int Compare (const void *a, const void *b) {
    int iA = atoi( (char*) *a );
    int iB = atoi( (char*) *b );
    return ( iB - iA );
}

now the qsort becomes like

CPP / C++ / C Code:

qsort( array, numLines, sizeof( array[0] ), &Compare );

Now the qsort sorts actually the pointers of the array. To understand the function Compare notice that the function gets pointers to pointers as an argument. Notice that array is not an array of chars but an array of pointers. so the quick sort gives pointers to pointers for the compare. Then the Compare gives the pointing targets to the atoi() functions..and finally the qsort rearranges the order of the pointers in array (a bit confusing to name an array as "array" some more descriptive name would be better)

Hyuga · #3 04-Aug-2005, 07:20

Thanks a lot again, maprich. Great explanation.

I have a problem yet. When I use your version of Compare, I get an error:

Warning:"Dereferencing void* pointer"
Error: void value not ignored as it ought to be

The bold lines have the problem.

Quote:

Originally Posted by maprich

CPP / C++ / C Code:

int Compare (const void *a, const void *b) {
[b]    int iA = atoi( (char*) *a );[/b]
[b]    int iB = atoi( (char*) *b );[/b]
    return ( iB - iA );
}

I see that you are using a double pointer, but in fact, I think that the function has to handle only 1D arrays, cause it have to compare strings. So maybe I have to get rid of one of the pointers. What do you think?

Dave Sinkula · #4 04-Aug-2005, 08:38

Quote:

Originally Posted by maprich

Your comparing function has a big confusion in the "return ..." line. However the whole thing should be modified because we are quick-sorting 2D arrays instead of 1D. So I suggest the following:

CPP / C++ / C Code:

int Compare (const void *a, const void *b) {
    int iA = atoi( (char*) *a );
    int iB = atoi( (char*) *b );
    return ( iB - iA );
}

This has undefined behavior on signed integer overflow, whereas the "big confusion" was intended to avoid that.

maprich · #5 04-Aug-2005, 08:42

Ok I had errors because I didn't actually compile my code.. However I did now and detected several small and some big errors.

The compiler protects the "const" variables so jealously that the conversions are difficult to make. But not impossible.. here is my entire code:

CPP / C++ / C Code:

int Compare( const void **a, const void **b )
{
    char *A = (char*)*a;
    char *B = (char*)*b;
    int iA = atoi( A );
    int iB = atoi( B );
    return ( iA - iB );
}

int main(int argc, char *argv[])
{
    char **array;
    int numLines = 3;
    int i;
    
    array = (char**)malloc( numLines*sizeof( *array ) );
    for( i=0; i<numLines; ++i ) array[i] = (char*)malloc( 4*sizeof( char ) );
    
    array[0] = "027";
    array[1] = "023";
    array[2] = "012";

    qsort( array, numLines, sizeof( array[0] ), (int(*)(const void*, const void*))&Compare );
    
    printf( "%s, %s, %s\n", array[0], array[1], array[2] );
}

maprich · #6 04-Aug-2005, 08:48

^^^ as you see inside the qsort I had to make that quite horrendous function typecast so that Compare() function could take pointers to pointers as a parameter... all that just so that atoi could get access to the actual strings.

also originally I forgot to typecast the malloc void pointers.. and in Compare() returnvalue was inverted.. meaning that if you do "return (iB-iA);" you get descending order and if you do "return (iA-iB);" you get ascending order.

Dave Sinkula · #7 04-Aug-2005, 08:51

CPP / C++ / C Code:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int Compare (const void *a, const void *b)
{
   char * const *x = a;
   char * const *y = b;
   int da = atoi(*x);
   int db = atoi(*y);
   return (da > db) - (da < db);
}

int main(void)
{
   size_t i, size = 3, length = 3 + 1;  /* +1 for \0 char*/
   char **array = malloc(size * sizeof *array);
   if ( array != NULL )
   {
      for ( i = 0; i < size; ++i )
      {
         array[i] = malloc(length);
         if ( !array[i] )
         {
            goto cleanup;
         }
      }

      /*assign random values for testing*/
      strcpy(array[0], "027");
      strcpy(array[1], "023");
      strcpy(array[2], "012");

      puts("before");
      for ( i = 0; i < size; ++i )
      {
         printf("array[%lu] = \"%s\"\n", (long unsigned)i, array[i]);
      }

      qsort(array, size, length, Compare);

      puts("after");
      for ( i = 0; i < size; ++i )
      {
         printf("array[%lu] = \"%s\"\n", (long unsigned)i, array[i]);
      }
      --i;

cleanup:
      do
      {
         free(array[i]);
      } while ( i-- > 0 );
      free(array);
   }
   return 0;
}

/* my output
before
array[0] = "027"
array[1] = "023"
array[2] = "012"
after
array[0] = "012"
array[1] = "023"
array[2] = "027"
*/

maprich · #8 04-Aug-2005, 08:58

Ok thanks dave I see your solution is better.. and I didn't first see the reason behind the "return (da > db) - (da < db);" My apologies.

Hyuga · #9 04-Aug-2005, 09:05

maprich, Dave, thank you very much.

Can I question one last thing? I have understand the function typecasting explanation from maprich, but I don't know the reason of this declaration Dave:

CPP / C++ / C Code:

char * const *x = a;

Maybe it is because a is a const void * and contains a char * variable?

Dave Sinkula · #10 04-Aug-2005, 09:17

Quote:

Originally Posted by Hyuga

I have understand the function typecasting explanation from maprich, but I don't know the reason of this declaration Dave:

CPP / C++ / C Code:

char * const *x = a;

Maybe it is because a is a const void * and contains a char * variable?

I get confused with this stuff too, but I think you nailed it.

If we had written a compare function for ints, we might use this:

CPP / C++ / C Code:

int compare(const void *a, const void *b)
{
   const int *x = a;
   const int *y = b;
   return( *x > *y ) - ( *x < *y ); /* or customize */
}

There is no need to discard the const-ness, and the value pointed to is an int. This could also be rewritten like this.

CPP / C++ / C Code:

int compare(const void *a, const void *b)
{
   int const *x = a;
   int const *y = b;
   return( *x > *y ) - ( *x < *y ); /* or customize */
}

Since the value being pointed to is a pointer to char, the int should be replaced by char *. But since you are comparing the intger value represented by the text pointed to by this pointer, you need the atoi step. (Although I would reconsider this approach since it would be a very costly sort that had to do these conversions for each compare.

CPP / C++ / C Code:

int Compare (const void *a, const void *b)
{
   char * const *x = a;
   char * const *y = b;
   int da = atoi(*x);
   int db = atoi(*y);
   return (da > db) - (da < db);
}

Thread Tools	Search this Thread
Show Printable Version Email this Page	Search this Thread: Advanced Search
Rate This Thread
Rate This Thread:

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
sorting numbers through array	zidanefreak01	C++ Forum	3	26-Jun-2005 02:41
Dynamic allocation of multi dimensional array	pointer	C Programming Language	7	13-May-2005 23:50
template comiling problems - need expert debugger!	crq	C++ Forum	1	01-Feb-2005 21:26
Sorting a 2D array c++	mike3340	C++ Forum	4	15-Dec-2003 13:35