Hyper

Algoritmos de ordenamiento
^
1. Introducción.
^
El ordenamiento es una labor común que realizamos continuamente. ¿Pero te has preguntado qué es ordenar? ¿No? Es que es algo tan corriente en nuestras vidas que no nos detenemos a pensar en ello. Ordenar es simplemente colocar información de una manera especial basándonos en un criterio de ordenamiento.
En la computación el ordenamiento dedatos también cumple un rol muy importante, ya sea como un fin en sí o como parte de otros procedimientos más complejos. Se han desarrollado muchas técnicas en este ámbito, cada una con características específicas, y con ventajas y desventajas sobre las demás. Aquí voy a mostrarte algunas de las más comunes, tratando de hacerlo de una manera sencilla y comprensible.
2. Conceptos Preliminares.
^Antes de comenzar a ver cada algoritmo vamos a ponernos de acuerdo en algunos conceptos, para que no haya confusiones:
* Clave: La parte de un registro por la cual se ordena la lista. Por ejemplo, una lista de registros con campos nombre, direccion y telefono se puede ordenar alfabéticamente de acuerdo a la clave nombre. En este caso los campos direccion y telefono no se toman en cuenta enel ordenamiento.
* Criterio de ordenamiento (o de comparación): EL criterio que utilizamos para asignar valores a los registros con base en una o más claves. De esta manera decidimos si un registro es mayor o menor que otro. En el pseudocódigo presentado más adelante simplemente se utilizarán los símbolos < y >, para mayor simplicidad.
* Registro: Un grupo de datos que forman la lista.Pueden ser datos atómicos (enteros, caracteres, reales, etc.) o grupos de ellos, que en C equivalen a las estructuras.
Cuando se estudian algoritmos de todo tipo, no sólo de ordenamiento, es bueno tener una forma de evaluarlos antes de pasarlos a código, que se base en aspectos independientes de la plataforma o el lenguaje. De esta manera podremos decidir cuál se adapta mejor a los requerimientosde nuestro programa. Así que veamos estos aspectos:
* Estabilidad: Cómo se comporta con registros que tienen claves iguales. Algunos algoritmos mantienen el orden relativo entre éstos y otros no. Veamos un ejemplo. Si tenemos la siguiente lista de datos (nombre, edad): "Pedro 19, Juan 23, Felipe 15, Marcela 20, Juan 18, Marcela 17", y la ordenamos alfabéticamente por el nombre con unalgoritmo estable quedaría así: "Felipe 15, Marcela 20, Marcela 17, Juan 23, Juan 18, Pedro 19". Un algoritmo no estable podría dejar a Juan 18 antes de Juan 23, o a Marcela 20 después de Marcela 17.
* Tiempo de ejecución: La complejidad del algoritmo, que no tiene que ver con dificultad, sino con rendimiento. Es una función independiente de la implementación. Te la voy a explicar brevemente:tenemos que identificar una operación fundamental que realice nuestro algoritmo, que en este caso es comparar. Ahora contamos cuántas veces el algoritmo necesita comparar. Si en una lista de n términos realiza n comparaciones la complejidad es O(n). (En realidad es un poco más complicado que eso, pero lo vamos a hacer así: recuerda que dije que te iba a explicar brevemente). Algunos ejemplos decomplejidades comunes son:
* O(1) : Complejidad constante.
* O(n2) : Complejidad cuadrática.
* O(n log(n)) : Complejidad logarítmica.
Ahora podemos decir que un algoritmo de complejidad O(n) es más rápido que uno de complejidad O(n2). Otro aspecto a considerar es la diferencia entre el peor y el mejor caso. Cada algoritmo se comporta de modo diferente de acuerdo a cómo se leentregue la información; por eso es conveniente estudiar su comportamiento en casos extremos, como cuando los datos están prácticamente ordenados o muy desordenados.
* Requerimientos de memoria: El algoritmo puede necesitar memoria adicional para realizar su labor. En general es preferible que no sea así, pero es común en la programación tener que sacrificar memoria por rendimiento.
Hay...