Ordenamiento genérico.

     Una vez que se ha transitado el camino de los arreglos, del ordenamiento por burbuja, de los apuntadores y de los apuntadores a función, se cuenta con un conjunto de herramientas bastante sólido para desarrollar nuevas cosas.

    Por otro lado, la mayoría de los algoritmos de ordenamiento trabajan sobre números enteros, pero en principio se podrían ordenar también números en punto flotante, cadenas, caracteres, etcétera. Todavía más: siempre que en una colección de datos exista una relación de orden, es decir, la determinación de un criterio para establecer un orden sobre ellos, es posible ordenar dicha colección.

    La consecuencia inmediata del planteamiento anterior nos debería conducir a lo siguiente: por cada colección de datos que se quiera ordenar, habría que introducir cambios significativos en la implementación del algoritmo, ya que dicha colección está representada mediante un arreglo y los arreglos tienen que ser de un tipo de datos; por lo que, al menos en principio, debería tener el mismo algoritmo de ordenamiento implementado para cada uno de los tipos de datos que se quieran ordenar.

    ¿Existe alguna forma de implementar una función de ordenamiento genérica que opere sobre arreglos cuyos elementos sean de cualquier tipo de datos siempre que se cuente con una relación de orden bien definida? La respuesta es que, con un poco de esfuerzo adicional, sí es posible.

    Por su simplicidad y porque es un algoritmo que se ha estudiado y desarrollado en el blog, en esta página se hará un breve recorrido por una implementación genérica en el lenguaje C del algoritmo de la burbuja.

Burbuja genérico.

    En el Ejemplo 7.11.1 se muestra una biblioteca de funciones con dicha implementación. Para su comprensión, es preciso que el lector haya revisado, estudiado y comprendido los temas referentes a arreglos, apuntadores y obviamente el algoritmo de la burbuja; aquí sólo nos centraremos en los aspectos concernientes a la implementación genérica.

    Lo primero a notar es la línea 18. Como no sabemos qué tipo de datos contendrá el arreglo se declara un apuntador a void, la cual es una forma en C de especificar al lenguaje que por el momento no haga ningún tipo de interpretación a los datos; por otro lado, necesitamos saber cuántos datos se van a considerar (n), de cuántos bytes es cada uno (size) y el criterio (apuntador a función) que se utilizará para realizar la comparación y establecer la relación de orden. Note que el apuntador a función también recibe apuntadores a void porque, una vez más, no se sabe el tipo de datos involucrado: eso se determinará hasta la ejecución y la invocación correspondiente.

    Para poder enviar los datos apropiados al apuntador de función (línea 26) y determinar si ese par de datos necesita ser intercambiado (línea 27), en las líneas 24-25 se obtienen en un formato de "byte crudo" (raw byte) las referencias al elemento i-ésimo e i-ésimo+1 del arreglo. El lenguaje C no tiene un tipo de dato byte pero no lo necesita: un byte en C es un unsigned char (un char sin signo, es decir 8 bits, i.e. 1 byte).

    Un void por sí mismo no puede ser interpretado, por lo que al hacer el cast, (líneas 24-25) lo estamos dotando de interpretación: bytes. La dirección inicial del arreglo (a) más el desplazamiento correspondiente (i) multiplicado por el número de bytes (size) del tipo de dato en cuestión proporciona la suma escalda que se necesita para cualquier tipo de dato. De hecho es lo que hace el compilador cuando traduce notación de arreglos a notación de apuntadores:

a[ i ] == *(a + i * size)

donde size es el tamaño en bytes del tipo de dato de a.

    Finalmente, la función intercambio (líneas 10-16) es la encargada de, como su nombre lo indica, realizar el intercambio entre a y b utilizando a la función de biblioteca memcpy y un buffer (área de memoria) auxiliar (línea 11). memcpy pertenece a la biblioteca string.h y básicamente copia áreas de memoria; se deja su documentación y detalles como ejercicio para el lector.

Invocación. 

    El Ejemplo 7.12.1 muestra un par de posibles usos del ordenamiento genérico anterior. Por cada tipo de dato a ordenar, se debe tener su correspondiente criterio de comparación que utilizará el apuntador de función: funciones comparaChar (líneas 38-43) y comparaInt (líneas 45-50) pero en principio, con el criterio apropiado, se podrían comparar y en consecuencia ordenar char, int, long, float, double, EMPLEADO, PERSONA, VACA, etcétera.

    Para el caso del ejemplo anterior, se tiene el criterio para un ordenamiento para char, y se tiene entre comentarios un ordenamiento para int (líneas 19-29). Se deja como ejercicio para el lector el probar este y otros criterios, así como sus correspondientes funciones de comparación en función de tipo de datos.