Função genérica para ordenar arrays

A função ordenar_array dada anteriormente ordena um array de números inteiros por ordem crescente. O ordenar_array não é uma função muito genérica porque se só serve para ordenar arrays de inteiros. Se quisermos ordenar um array que não seja de inteiros temos de escrever uma nova função.

Em C, é possível fazer uma função que ordene um array de elementos de um tipo T genérico, mas isso é uma matéria avançada e que não vamos estudar nesta cadeira. No entanto, a biblioteca stdlib.h já tem essa tal função genérica definida. A função chama-se qsort e é uma implementação de um algoritmo de ordenação famoso chamado quicksort e que vão ter oportunidade de estudar na cadeira de Programação II. A função qsort tem 4 argumentos:

  1. o nome do array.
  2. o número de elementos do array.
  3. o número de bytes que cada elemento do array ocupa.
  4. o nome de uma função de comparação.

A função de comparação deve ter 2 argumentos do tipo const void *. A função deve retornar,

Exemplos:

Para ordenar um array a de n inteiros teríamos de escrever uma função que compare 2 elementos do tipo int. Vamos chamar a essa função intcomp. Aqui vai ela,

    int intcomp( const void *x, const void *y )
    {
       int *xx, *yy;

       xx = (int *) x;
       yy = (int *) y;

       if( *xx < *yy ) return -1;
       if( *xx == *yy ) return 0;
       if( *xx > *yy ) return 1;
    }

    main()
    {
      int a[100];
      int n;
     
      ...
      qsort( a, n, sizeof(int), intcomp );
      ...
    }

Nota: a função intcomp podia ter sido feita de modo mais eficiente. Ficaria assim,

    int intcomp( const void *x, const void *y )
    {
       int *xx, *yy;

       xx = (int *) x;
       yy = (int *) y;

       return (*xx - *yy);
    }

Nota: a palavra const significa que o argumento (no nosso exemplo, x) não pode ser alterado no interior da função. Como os argumentos são do tipo void *, temos de fazer um casting para o tipo apropriado (no nosso exemplo, int *). O void * é uma espécie de apontador genérico. Ao fazer o casting, ficamos com um apontador para um tipo de dados específico.

Se quisermos ordenar um array de elementos que não sejam inteiros, a única coisa que é necessário fazer é escrever a nova função de comparação. Por exemplo, para ordenar um array de datas, teríamos de fazer qualquer coisa deste estilo,

    typedef struct
    {
       int dia, mes, ano;
    } data;

    int datacomp( const void *x, const void *y )
    {
       /* função para comparar duas datas */

       ...
    }

    main()
    {
      data d[100];
      int n;
     
      ...
      qsort( a, n, sizeof(data), datacomp );
      ...
    }

Tentem completar o exercício.

Apontadores para apontadores

Vamos supor que queríamos ter uma variável chamada nomes que permitisse guardar uma lista de nomes de pessoas. Aqui vai uma tentativa.

    char nomes[100][30];

nomes é um array que permite guardar no máximo 100 strings, cada qual com o tamanho máximo de 30 caracteres. Esta solução corresponde à seguinte figura.

e tem 2 inconvenientes: (1) o número máximo de nomes que podemos guardar é 100, e (2) o número máximo de caracteres para cada nome é 30.

Como já sabemos fazer alocação dinâmica de memória, podemos arranjar uma solução mais flexível. De modo a não ter a limitação de 30 caracteres por nome, podemos declarar a variável nomes como sendo um array de apontadores para char. A ideia é que cada elemento do array vai ficar a apontar para um nome cujo espaço será alocado dinamicamente. Aqui vai o código,

    char *nomes[100];

    nomes[0] = (char *) malloc( (1+strlen("susana")) * sizeof(char) );
    if( nomes[0] == NULL )
      erro("...");
    strcpy( nomes[0], "susana" );

    nomes[1] = (char *) malloc( (1+strlen("toze")) * sizeof(char) );
    if( nomes[1] == NULL )
      erro("...");
    strcpy( nomes[1], "toze" );

    ...
    
    /* no final deve-se libertar a memória */
    ...

Vamos supor que temos apenas 3 nomes: "susana", "toze" e "miguel angelo". O desenho correspondente seria,

Esta solução já é mais flexível que a primeira. Agora, cada nome pode ter mais do que 30 caracteres. No entanto, continuamos com a limitação de só podermos ter no máximo 100 nomes. Para resolver o problema, temos de declarar a variável nomes como sendo um apontador para apontador para char. Deste modo, o array de apontadores também é alocado dinamicamente.

    char **nomes;
    int n;

    printf("Quantos nomes queres guardar? ");
    scanf("%d",&n);
    
    /* alocar memória para um array de 'n' apontadores para char */

    nomes = (char **) malloc( n * sizeof(char *) );
    if( nomes == NULL )
      erro("...");

    /* alocar memória para cada nome */
    
    nomes[0] = (char *) malloc( (1+strlen("susana")) * sizeof(char) );
    if( nomes[0] == NULL )
      erro("...");
    strcpy( nomes[0], "susana" );

    nomes[1] = (char *) malloc( (1+strlen("toze")) * sizeof(char) );
    if( nomes[1] == NULL )
      erro("...");
    strcpy( nomes[1], "toze" );

    ...


    /* libertar a memória usada pelos 'n' nomes */
    for( i=0; i<n; i++ )
       free( nomes[i] );

    /* libertar a memória usada pelo array de apontadores */
    free( nomes );

O desenho correspondente seria,

Agora já podemos ter mais do que 100 nomes, e cada nome pode ter o número de caracteres que quisermos. Esta solução, além de ser mais flexível é mais eficiente porque apenas estamos a reservar espaço para a informação que é estritamente necessária. Estes aspectos não são muito importantes quando temos apenas meia dúzia de dados. Em contrapartida, se estivermos a manipular grandes volumes de informação, torna-se fundamental usar a memória de modo eficiente.

Recomendação...

A matéria de apontadores é dos tópicos mais delicados da programação. Normalmente, os alunos levam algum tempo até dominarem esta matéria por completo. A sintaxe do C assusta um bocado, mas o conceito de apontador é simples. Sempre que estiverem baralhados, recomendo que façam uns bonecos, tal e qual como eu fiz ao escrever estes apontamentos.

O uso de apontadores em programação requer bastante cuidado. Caso contrário, os programas começam a estoirar. Devem programar com cuidado e testar os programas de modo conveniente de modo a ficarem seguro que os programas não têm bugs.