Algoritmos de Ordenación

En este articulo se estudiará el problema de ordenar un array de elementos sobre los cuales se puede establecer una relación de orden.

Los algoritmos de este documento serán escritos en C y serán intercambiables entre si; es decir, todos aceptarán los mismos parámetros: un array A de datos y un entero que representa el tamaño del array.

Si bien en todo este documento se mostrará como ordenar de forma creciente (de menor a mayor), esperamos que el lector no tenga problemas realizar las modificaciones pertinentes (que deberán ser obvias) en los algoritmos para poder ordenar de forma decreciente.

El array de entrada A tendrá elementos de tipo Dato los cuales podrán ser cualquier tipo de dato representable (una estructura, un objeto de una clase en particular, un número, un string, etc). Dicho array será usado al estilo C, es decir los índices de los N lementos de A serán 0, 1, 2, ..., N-1.

También se utilizará el operador de asignación de manera especial en algunos casos.

Por ejemplo, en el siguiente segmento de código, en tmp se almacenará una copia del iésimo elemento del array A de entrada.

Dato tmp;

/* ... */

tmp = A[i];

Junto con la descripción de cada algoritmo también se discutirá el orden de tiempo de ejecución del mismo. Se utilizará para esto la notación de ordenes de magnitud "O grande" ("big oh"). La medición de estos tiempos ha sido hecha considerando solamente la cantidad de comparaciones, asignaciónes, etc que impliquen elementos del array de datos: o sea, las cotas de tiempo sólo están en función del tamaño del conjunto de datos. Puesto que estos pueden ser arbitrariamente complejos, no se consideran los tiempos de operaciones sobre ellos. Por ejemplo, (la velocidad de un algoritmo será distinta para conjuntos de enteros que para conjuntos de reales, puesto que las operaciones sobre estos últimos por lo general son más lentas que sobre los primeros).

El documento completo, junto con el código de los algoritmos y una pequeña aplicación lo puedes descargar haciendo clic en la imagen: