ORDENAMIENTOS
Concepto
de ordenamiento
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 de datos 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.
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 en el 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 requerimientos de 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 un algoritmo 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 de complejidades 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 le entregue 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 bastantes otros aspectos que se pueden tener en cuenta, pero nosotros
nos vamos a quedar con ésos.
Por último estableceremos algunas convenciones sobre el pseudocódigo:
- Vamos a ordenar la lista en
forma ascendiente, es decir, de menor a mayor. Obviamente es esencialmente
lo mismo que hacerlo en forma inversa.
- La forma de intercambiar los
elementos depende de la estructura de datos: si es un arreglo (dinámico o
estático) es necesario guardar una copia del primer elemento, asignarle el
segundo al primero y el temporal al segundo. La variable temporal es
necesaria, porque de lo contrario se perdería uno de los elementos. Si la
estructura es una lista dinámica el procedimiento es parecido, pero se
utilizan las direcciones de los elementos. En el pseudocódigo
se utilizará el primer método.
- La lista se manejará como un
arreglo de C: si tiene TAM elementos, el primer elemento es lista[0] y el
último es lista[TAM-1]. Esto será así para todo el pseudocódigo
presentado en este artículo.
