Wiki CC3301

No existen variables de tipo “función”, pero es posible tener una variable que es un puntero a una función. Esto es especialmente útil como parámetros para funciones. El siguiente es un ejemplo de un función de ordenamiento genérico, es decir permite ordenar objetos de acuerdo a un criterio definido por una función que se se recibe como parámetro:

  /* ordena datos de cualquier tipo usando Quicksort */

  void swap(void *v[], int i, int j) {
    void *aux;

    aux= v[i];
    v[i]= v[j];
    v[j]= aux;
  }

  void qsort(void *a[], int left, int right,
             int (*compare)(void *, void *)) {
    int i, last;

    if (left>=right)
      return;

    swap(a, left, (left+right)/2);
    last= left;

    /*
      +--+-----------+--------+--------------+
      |  |///////////|\\\\\\\\|              |
      +--+-----------+--------+--------------+
      left        last         i         right
    */

    for (i= left+1; i<=right; ++i)
      if ((*compare)(a[i], a[left])<0)
        swap(a, ++last, i);
    swap(a, left, last);

    qsort(a, left, last-1, compare);
    qsort(a, last+1, right, compare);
  }

La declaración int (*compare)(void *, void *) es para declarar un puntero a una función. Esto se lee de la siguiente forma. Dados 2 punteros a cualquier tipo p y q, la expresion (*compare)(p, q) es de tipo int.

El siguiente programa utiliza la función anterior para ordenar líneas lexicográficamente:

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

  void qsort(void *a[], int left, int right,
             int (*compare)(void *, void *));
             
  int main(int argc, char **argv) {
    int j;
    int (*compare)(void *, void *)= (int (*)(void *, void*)) strcmp; /* Ver nota */

    qsort((void**)argv, 1, argc-1, compare);

    for (j= 1; j<argc; ++j)
      printf("%s\n", argv[j]);
  }

La expresión (int (*)(void *, void*)) es un cast. Se necesita para compatibilizar strcmp con el tipo de la variable asignada. Si se pasa directamente strcmp a qsort, el compilador podría reclamar conflicto de tipos.

Otra forma de hacer esto mismo:

  typedef int (*Comparator)(void *, void *);

  void qsort(void *a[], int left, int right, Comparator compare) {
    ...
  }
  
  int main() {
    ...
    Comparator compare= (Comparator)strcmp;
    ...
  }

Lo cual es mucho más legible.

Por último también se puede usar una función de comparación de strings propia que reciba como parámetros punteros a void:

  int mistrcmp(void *p1, void *p2) {
    char *s1= (char*)p1;
    char *s2= (char*)p2;
    return strcmp(s1, s2);
  }

Ahora se puede llamar a qsort especificando como comparador mistrcmp sin tener que aplicar un complicado cast:

    qsort((void**)argv, 1, argc-1, mistrcmp);

Este ejemplo ordena los strings por valor numérico:

  int numcmp(void *s1, void *s2) /* compara numricamente */ {
    int i1, i2;

    i1= atoi((char*)s1);
    i2= atoi((char*)s2);

    return i1<i2? -1 : i1==i2 ? 0 : 1;
  }

  int main(int argc, char **argv) {
    int j;

    qsort((void**)argv, 1, argc-1, numcmp);

    for (j= 1; j<argc; ++j)
      printf("%s\n", argv[j]);
  }

Estudie en los apuntes de Patricio Poblete un programa que recibe la opción “-n” para seleccionar el criterio de ordenamiento numérico, mientras que por omisión ordena alfabéticamente.

¿Cómo se podría usar qsort para ordenar un arreglo de enteros? Por ejemplo tenemos este arreglo:

  int a[6]= {3, 7, 8, 10, 1, 2};

Hay 2 formas: la elegante y la abreviada. Primero veamos la elegante. En teoría no podemos usar directamente el arreglo de enteros porque qsort recibe un arreglo de punteros, no enteros. Entonces tenemos que fabricar un arreglo adicional que contenga punteros a los enteros:

  int *ap[6]= { &a[0], &a[1], &a[2], &a[3], &a[4], &a[5] };

Y ahora programamos la función de comparación y el main:

  int intcmp(void *p1, void *p2) {
    int i1= *(int*)p1;
    int i2= *(int*)p2;
    if (i1<i2)
      return -1;
    else if (i1==i2)
      return 0;
    else
      return 1;
  }
  
  int main() {
    int i;
    qsort(ap, 0, 5, intcmp); /* Ojo: ordena el arreglo ap, no a */
    for (i= 0; i<6; i++)
      printf("%d\n", *p[i]);
    return 0;
  }