Sorting a 2D array with qsort

问题:

I'm trying to sort 2d array. First i sort it by column, then by rows. Column by column is working but row by row not. What's wrong in this code?

int scmpr (const void *a, const void *b){ 
return strcmp((const char*)a, (const char*)b);
}

int main(void){
  int i,j;

  char **tab;
  tab=(char**)malloc(sizeof(char*)* 10); 

  for(i=0; i<10; i++){
    tab[i]=(char*)malloc(sizeof(char)*15);
  }

  for(i=0; i<10; i++){
    for(j=0; j<15; j++){
      tab[i][j]=rand()%20+'b';
      printf("%c ", tab[i][j]);
    }
    puts("");
  }
  for (i = 0; i<10; i++){
    qsort(&tab[i][0], 15, sizeof(char), scmpr); 
  }
  qsort(tab, 10, sizeof(char), scmpr); //<-- doesn't work

    for(i=0; i<10; i++){
      for(j=0; j<15; j++){
        printf("%c ", tab[i][j]);
      }
    puts("");
    } 
  puts("");
  return 0;
  }

回答1:

I think that you mean the following

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

#define M   10
#define N   15

int ccmp( const void *lhs, const void *rhs )
{
    unsigned char c1 = *( const unsigned char *)lhs;
    unsigned char c2 = *( const unsigned char *)rhs; 

    if ( c1 < c2 ) return -1;
    else if ( c2 < c1 ) return 1;
    else return 0;
}

int scmp( const void *lhs, const void *rhs )
{
    return strcmp( *( const char ** )lhs, *( const char ** )rhs );
}

int main( void ) 
{
    char **tab;
    tab = ( char** )malloc( M * sizeof( char* ) ); 

    for ( size_t i = 0; i < M; i++ )
    {
        tab[i] = ( char* )malloc( N * sizeof( char ) );
    }

    srand( ( unsigned int )time( NULL ) );

    for ( size_t i = 0; i < M; i++ )
    {
        for ( size_t j = 0; j < N - 1; j++ )
        {
            tab[i][j] = rand() % ( 'Z' - 'A' + 1 ) + 'A';
        }
        tab[i][N-1] = '\0';
    }

    for ( size_t i = 0; i < M; i++ )
    {
        printf( "%s\n", tab[i] );
    }

    printf( "\n" );

    for ( size_t i = 0; i < M; i++ )
    {
        qsort( tab[i], N - 1, sizeof( char ), ccmp ); 
    }
    qsort( tab, M, sizeof( char * ), scmp );

    for ( size_t i = 0; i < M; i++ )
    {
        printf( "%s\n", tab[i] );
    }

    printf( "\n" );

    for ( size_t i = 0; i < M; i++ ) free( tab[i] );
    free( tab );

    return 0;
}

The program output might look the following way

DJSKLJOHGHEANW
ZSDZJZXCKGYOVF
LHEOQYAEHOLPYR
PLORDTQOSNQFVP
TQUEYAVQYVUHKH
WIZOVPHYKXPEMF
JHUFARLARGQSEN
BOWYYXOTMVTYUI
DIOOPKVPDHPXPI
PTXQJVQHTGCHDY

AAEFGHJLNQRRSU
ADEGHHJJKLNOSW
AEEHHLLOOPQRYY
AEHHKQQTUUVVYY
BIMOOTTUVWXYYY
CDFGJKOSVXYZZZ
CDGHHJPQQTTVXY
DDHIIKOOPPPPVX
DFLNOOPPQQRSTV
EFHIKMOPPVWXYZ

回答2:

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

int scmpr (const void *a, const void *b){//receive char **
    return strcmp(*(const char**)a, *(const char**)b);
}
int ccmpr (const void *a, const void *b){//compare one char
    unsigned char x = *(unsigned char *)a;
    unsigned char y = *(unsigned char *)b;
    return (x > y) - (x < y);
}

int main(void){
    int i,j;

    char **tab;
    tab=(char**)malloc(sizeof(char*)* 10); 

    for(i=0; i<10; i++){
        tab[i]=(char*)malloc(sizeof(char)*16);//+1 for NUL char to use strcmp
    }

    for(i=0; i<10; i++){
        for(j=0; j<15; j++){
            tab[i][j]=rand()%20+'b';
            printf("%c ", tab[i][j]);
        }
        tab[i][j] = 0;//set NUL
        puts("");
    }
    for (i = 0; i<10; i++){
        qsort(&tab[i][0], 15, sizeof(char), ccmpr); 
    }
    qsort(tab, 10, sizeof(char*), scmpr);//element is char*

    puts("");

    for(i=0; i<10; i++){
        for(j=0; j<15; j++){
            printf("%c ", tab[i][j]);
        }
        puts("");
    }
    //deallocate
    return 0;
}

回答3:

qsort

Sort elements of array

Sorts the num elements of the array pointed by base, each element size bytes long, using the compar function to determine the order.

The sorting algorithm used by this function compares pairs of elements by calling the specified compar function with pointers to them as argument.

The function does not return any value, but modifies the content of the array pointed by base reordering its elements as defined by compar.

The order of equivalent elements is undefined.

As a result, it will sort each group of 15 elements in the list of i, as a normal array which will give you the result you see. However, since the "j" are separated. What you would need to do is to create a single dimensioned array table for each row from the group for each value of i. Then after doing the qsort on each singly dimensioned row, move them appropriatly into the original 2D table.

qsort(tab, 10, sizeof(char*), scmpr);//element is char*

will qsort the first 10 (character) elements of tab and not the rows as you intended.