Considera el siguiente problema: quieres escribir una función para ordenar virtualmente cualquier colección de datos que pueda guardarse en un array. Esto podría ser un array de cadenas, o de enteros, o de floats, o incluso de estructuras. El algoritmo de ordenación puede ser para todos el mismo. Por ejemplo, podría ser un algoritmo de ordenación de burbuja simple, o de tipo shell (más complicado) o el algoritmo de ordenación quick sort. Para nuestro propósito, aquí veremos una ordenación de burbuja simple.
Sedgewick [1] escribió en C la ordenación de burbuja utilizando una función que, pasándola un puntero a un array, lo ordena. Vamos a ver la función bubble() en el siguiente programa bubble_1.c:
/*-------------------- bubble_1.c --------------------*/
/* Programa bubble_1.c de PTRTUT10.HTM 6/13/97 */
#include <stdio.h>
int arr[10] = { 3,6,1,2,3,8,4,1,7,2};
void bubble(int a[], int N);
int main(void)
{
int i;
putchar('\n');
for (i = 0; i < 10; i++)
{
printf("%d ", arr[i]);
}
bubble(arr,10);
putchar('\n');
for (i = 0; i < 10; i++)
{
printf("%d ", arr[i]);
}
return 0;
}
void bubble(int a[], int N)
{
int i, j, t;
for (i = N-1; i >= 0; i--)
{
for (j = 1; j <= i; j++)
{
if (a[j-1] > a[j])
{
t = a[j-1];
a[j-1] = a[j];
a[j] = t;
}
}
}
}
/*---------------------- fin bubble_1.c -----------------------*/
La ordenación de burbuja es una de las más simples. El algoritmo
escanea el array desde el segundo hasta el último elemento,
comparando cada uno con el que le precede. Si el predecesor es
mayor al actual elemento, se intercambian quedando el mayor más
cerca del fin del array. El resultado de la primera pasada es
que el elemento mayor queda el último en el array. El array
ahora queda limitado a todos los elementos menos el último y se
repite el proceso. En la siguiente pasada, el siguiente elemento
mayor quedará como predecesor del elemento mayor anterior. El proceso
se repite un número de veces igual al número de elementos menos
uno. El resultado es un array ordenado.
Nuestra función está diseñada para ordenar un array de enteros, primero comparando los enteros y después utiliza un entero temporal para realizar el intercambio. Lo que vamos a ver ahora es si podemos convertir este código para utilizar cualquier tipo de dato, no sólo enteros.
A la vez, no queremos analizar nuestro algoritmo y el código correspondiente cada vez que queramos utilizarlo. Empezaremos creando una nueva función de comparación sustituyendo la parte de la comparación dentro de la función bubble() con la llamada a la nueva función, así no hará falta reescribir las partes relacionadas del algoritmo actual. El resultado lo vemos en bubble_2.c:
/*---------------------- bubble_2.c -------------------------*/
/* Programa bubble_2.c de PTRTUT10.HTM 6/13/97 */
/* Separación de la función de comparación */
#include <stdio.h>
int arr[10] = { 3,6,1,2,3,8,4,1,7,2};
void bubble(int a[], int N);
int compare(int m, int n);
int main(void)
{
int i;
putchar('\n');
for (i = 0; i < 10; i++)
{
printf("%d ", arr[i]);
}
bubble(arr,10);
putchar('\n');
for (i = 0; i < 10; i++)
{
printf("%d ", arr[i]);
}
return 0;
}
void bubble(int a[], int N)
{
int i, j, t;
for (i = N-1; i >= 0; i--)
{
for (j = 1; j <= i; j++)
{
if (compare(a[j-1], a[j]))
{
t = a[j-1];
a[j-1] = a[j];
a[j] = t;
}
}
}
}
int compare(int m, int n)
{
return (m > n);
}
/*--------------------- fin de bubble_2.c -----------------------*/
Si el objetivo es hacer que nuestra rutina de ordenación sea
independiente del tipo de datos, una forma de hacerlo es utilizar
punteros de tipo void para apuntar a los datos en lugar de utilizar
el tipo de dato entero. Para ello, modifiquemos algunas cosas del
código anterior para incorporar punteros, empezando con los de
tipo entero.
/*----------------------- bubble_3.c -------------------------*/
/* Programa bubble_3.c de PTRTUT10.HTM 6/13/97 */
#include <stdio.h>
int arr[10] = { 3,6,1,2,3,8,4,1,7,2};
void bubble(int *p, int N);
int compare(int *m, int *n);
int main(void)
{
int i;
putchar('\n');
for (i = 0; i < 10; i++)
{
printf("%d ", arr[i]);
}
bubble(arr,10);
putchar('\n');
for (i = 0; i < 10; i++)
{
printf("%d ", arr[i]);
}
return 0;
}
void bubble(int *p, int N)
{
int i, j, t;
for (i = N-1; i >= 0; i--)
{
for (j = 1; j <= i; j++)
{
if (compare(&p[j-1], &p[j]))
{
t = p[j-1];
p[j-1] = p[j];
p[j] = t;
}
}
}
}
int compare(int *m, int *n)
{
return (*m > *n);
}
/*------------------ fin de bubble3.c -------------------------*/
Fíjate en los cambios. Ahora estamos pasando un puntero de tipo
entero (o un array de enteros) a bubble(). Dentro de la
función bubble estamos pasando punteros a los elementos del
array que queremos comparar con la función de comparación. Y,
por supuesto, desreferenciamos estos punteros en nuestra función
compare() para realizar la comparación actual. Lo siguiente
será convertir los punteros en bubble() a punteros de tipo
void para que la función no tenga en cuenta el tipo. Esto lo
vemos en bubble_4.
/*------------------ bubble_4.c ----------------------------*/
/* Programa bubble_4.c de PTRTUT10,HTM 6/13/97 */
#include <stdio.h>
int arr[10] = { 3,6,1,2,3,8,4,1,7,2};
void bubble(int *p, int N);
int compare(void *m, void *n);
int main(void)
{
int i;
putchar('\n');
for (i = 0; i < 10; i++)
{
printf("%d ", arr[i]);
}
bubble(arr,10);
putchar('\n');
for (i = 0; i < 10; i++)
{
printf("%d ", arr[i]);
}
return 0;
}
void bubble(int *p, int N)
{
int i, j, t;
for (i = N-1; i >= 0; i--)
{
for (j = 1; j <= i; j++)
{
if (compare((void *)&p[j-1], (void *)&p[j]))
{
t = p[j-1];
p[j-1] = p[j];
p[j] = t;
}
}
}
}
int compare(void *m, void *n)
{
int *m1, *n1;
m1 = (int *)m;
n1 = (int *)n;
return (*m1 > *n1);
}
/*------------------ fin de bubble_4.c ---------------------*/
En compare() hemos realizado una conversión del puntero
de tipo void al actual tipo que estamos ordenando (int *), y
como veremos después, esto es correcto. Como estamos pasando
un puntero que apunta a un array de enteros (int *p) como
parámetro a bubble(), tenemos que convertir esos
punteros a void cuando los pasamos a compare().
Como queremos que el primer parámetro de bubble() sea también un puntero de tipo void, esto implica que dentro de bubble() hay que hacer algo con la variable t, que actualmente es un entero. Además, cuando usamos t = p[j-1]; es necesario conocer el tipo de p[j-1] para saber cuantos bytes hay que copiar a la variable t (o la que utilicemos para realizar el reemplazo).
Actualmente en bubble_4.c, dentro de bubble() sabemos que el tipo de dato para ordenar (y por tanto el tamaño de cada elemento individual) se obtiene a partir del hecho de que el primer parámetro es un puntero de tipo entero. Si queremos utilizar bubble() con cualquier tipo de dato, necesitamos que ese puntero sea de tipo void, pero al hacerlo, vamos a perder información relativa al tamaño de los elementos individuales del array. Por ello, en bubble_5.c vamos a agregar un parámetro independiente para manejar esta información.
Los cambios que tiene bubble_5.c respecto a bubble_4.c son, quizás, más numerosos que los realizados antes. Por ello es conveniente comparar con cuidado los dos módulos para dar con las diferencias.
/*---------------------- bubble_5.c ---------------------------*/
/* Programa bubble_5.c de PTRTUT10.HTM 6/13/97 */
#include <stdio.h>
#include <string.h>
long arr[10] = { 3,6,1,2,3,8,4,1,7,2};
void bubble(void *p, size_t width, int N);
int compare(void *m, void *n);
int main(void)
{
int i;
putchar('\n');
for (i = 0; i < 10; i++)
{
printf("%d ", arr[i]);
}
bubble(arr, sizeof(long), 10);
putchar('\n');
for (i = 0; i < 10; i++)
{
printf("%ld ", arr[i]);
}
return 0;
}
void bubble(void *p, size_t width, int N)
{
int i, j;
unsigned char buf[4];
unsigned char *bp = p;
for (i = N-1; i >= 0; i--)
{
for (j = 1; j <= i; j++)
{
if (compare((void *)(bp + width*(j-1)),
(void *)(bp + j*width))) /* 1 */
{
/* t = p[j-1]; */
memcpy(buf, bp + width*(j-1), width);
/* p[j-1] = p[j]; */
memcpy(bp + width*(j-1), bp + j*width , width);
/* p[j] = t; */
memcpy(bp + j*width, buf, width);
}
}
}
}
int compare(void *m, void *n)
{
long *m1, *n1;
m1 = (long *)m;
n1 = (long *)n;
return (*m1 > *n1);
}
/*--------------------- fin de bubble_5.c ---------------------*/
He cambiado el tipo de datos del array de int a long
para ver los cambios necesarios en la función compare().
Dentro de bubble() he eliminado la variable t (lo
que hubiera supuesto cambiarla de tipo int al tipo
long). He añadido un buffer con un tamaño de 4 caracteres
sin signo para alojar un long (esto cambiará en las futuras
modificaciones de este código). El puntero caracter sin signo
*bp se utiliza para apuntar a la base del array a ordenar,
es decir, al primer elemento de ese array.
También he modificado lo que se pasa a compare(), y cómo se realiza el cambio de elementos que indica la comparación. El uso de memcpy() y la notación de punteros en lugar de la notación de arrays permite reducir la sensibilidad al tipo.
De nuevo, para tener una mejor compresión de lo que sucede y porqué, es necesaria una atenta comparación entre bubble_5.c y bubble_4.c
Ahora vamos a ver a bubble_6.c donde utilizaremos la misma función bubble() de bubble_5.c, pero para ordenar cadenas en lugar de enteros largos (long). Obviamente tenemos que cambiar la función de comparación, pues la comparación entre cadenas y la comparación entre enteros largos es distinta. Además, en bubble_6.c hemos eliminado las líneas dentro de bubble() que estaban comentadas en bubble_5.c.
/*--------------------- bubble_6.c ---------------------*/
/* Programa bubble_6.c de PTRTUT10.HTM 6/13/97 */
#include <stdio.h>
#include <string.h>
#define MAX_BUF 256
char arr2[5][20] = { "Mickey Mouse",
"Donald Duck",
"Minnie Mouse",
"Goofy",
"Ted Jensen" };
void bubble(void *p, int width, int N);
int compare(void *m, void *n);
int main(void)
{
int i;
putchar('\n');
for (i = 0; i < 5; i++)
{
printf("%s\n", arr2[i]);
}
bubble(arr2, 20, 5);
putchar('\n\n');
for (i = 0; i < 5; i++)
{
printf("%s\n", arr2[i]);
}
return 0;
}
void bubble(void *p, int width, int N)
{
int i, j, k;
unsigned char buf[MAX_BUF];
unsigned char *bp = p;
for (i = N-1; i >= 0; i--)
{
for (j = 1; j <= i; j++)
{
k = compare((void *)(bp + width*(j-1)), (void *)(bp + j*width));
if (k > 0)
{
memcpy(buf, bp + width*(j-1), width);
memcpy(bp + width*(j-1), bp + j*width , width);
memcpy(bp + j*width, buf, width);
}
}
}
}
int compare(void *m, void *n)
{
char *m1 = m;
char *n1 = n;
return (strcmp(m1,n1));
}
/*------------------- fin de bubble_6.c ---------------------*/
Como se da el hecho de que bubble() no tiene ninguna
modificación desde bubble_5.c, esto indica que esta función puede
ordenar una gran variedad de tipos de datos. Lo que queda por
hacer es pasar a bubble() el nombre de la función de comparación
que queremos usar para que pueda ser verdaderamente universal.
Así como el nombre de un array es la dirección de su primer elemento
en el segmento de datos, el nombre de una función está dentro de la
dirección de esa función en el segmento de código. Por lo tanto
necesitamos utilizar un puntero a una función, que en este caso es
la función de comparación.
Los punteros a funciones deben coincidir con el número y tipos de parámetros y el tipo del valor de retorno de la función a donde apunten. En nuestro caso declaramos nuestro puntero a función así:
int (*fptr)(const void *p1, const void *p2);Fíjate que si escribimos:
int *fptr(const void *p1, const void *p2);
tendríamos un prototipo de función para una función que devuelve
un puntero de tipo int. Esto se produce porque en C, el
operador paréntesis () tiene una precedencia mayor que el operador
de puntero *. Indicamos que es una declaración de un puntero a
función colocando los paréntesis alrededor de la cadena (*fptr).
Ahora modificaremos nuestra declaración de bubble() agregando como cuarto parámetro un puntero a función del tipo apropiado. El prototipo de la función sería:
void bubble(void *p, int width, int N,
int(*fptr)(const void *, const void *));
Cuando llamamos a bubble(), insertamos el nombre de la
función de comparación que queramos usar. El código de bubble_7.c
muestra como esta forma permite utilizar la misma función
bubble() para ordenar diferentes tipos de datos.
/*------------------- bubble_7.c ------------------*/
/* Programa bubble_7.c de PTRTUT10.HTM 6/10/97 */
#include <stdio.h>
#include <string.h>
#define MAX_BUF 256
long arr[10] = { 3,6,1,2,3,8,4,1,7,2};
char arr2[5][20] = { "Mickey Mouse",
"Donald Duck",
"Minnie Mouse",
"Goofy",
"Ted Jensen" };
void bubble(void *p, int width, int N,
int(*fptr)(const void *, const void *));
int compare_string(const void *m, const void *n);
int compare_long(const void *m, const void *n);
int main(void)
{
int i;
puts("\nBefore Sorting:\n");
for (i = 0; i < 10; i++) /* muestra enteros largos */
{
printf("%ld ",arr[i]);
}
puts("\n");
for (i = 0; i < 5; i++) /* muestra cadenas */
{
printf("%s\n", arr2[i]);
}
bubble(arr, 4, 10, compare_long); /* ordena enteros largos */
bubble(arr2, 20, 5, compare_string); /* ordena cadenas */
puts("\n\nAfter Sorting:\n");
for (i = 0; i < 10; i++) /* muestra enteros largos ordenados */
{
printf("%d ",arr[i]);
}
puts("\n");
for (i = 0; i < 5; i++) /* muestra cadenas ordenadas */
{
printf("%s\n", arr2[i]);
}
return 0;
}
void bubble(void *p, int width, int N,
int(*fptr)(const void *, const void *))
{
int i, j, k;
unsigned char buf[MAX_BUF];
unsigned char *bp = p;
for (i = N-1; i >= 0; i--)
{
for (j = 1; j <= i; j++)
{
k = fptr((void *)(bp + width*(j-1)), (void *)(bp + j*width));
if (k > 0)
{
memcpy(buf, bp + width*(j-1), width);
memcpy(bp + width*(j-1), bp + j*width , width);
memcpy(bp + j*width, buf, width);
}
}
}
}
int compare_string(const void *m, const void *n)
{
char *m1 = (char *)m;
char *n1 = (char *)n;
return (strcmp(m1,n1));
}
int compare_long(const void *m, const void *n)
{
long *m1, *n1;
m1 = (long *)m;
n1 = (long *)n;
return (*m1 > *n1);
}
/*----------------- fin de bubble_7.c -----------------*/