Algoritmos de Ordenamiento

[C con Clase] [1 Burbuja]

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 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.

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 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.

Bien, ahora que ya tenemos todo claro vamos a lo que nos interesa...

3. Algoritmos más comunes.

La siguiente es una tabla comparativa de algunos algoritmos de ordenamiento.
Si quieres saber más sobre alguno en particular haz un click sobre su nombre. En
cada página encontrarás una descripción, pseudocódigo y un análisis sobre su
rendimiento, ventajas y desventajas.

(Quizás quieras bajar ahora la demostración para ir
observándola a medida que vayas leyendo)

Tabla comparativa de algoritmos

Nombre

Complejidad

Estabilidad

Memoria adicional

Ordenamiento Burbuja
(Bubblesort)

O(n2)

Estable

No

Ordenamiento por
Selección

O(n2)

No Estable

No

Ordenamiento por
Inserción

O(n2)

Estable

No

Ordenamiento Rápido
(Quicksort)

O(n * log2(n))

No Estable

No

4. Eligiendo el más adecuado.

Ahora ya conoces una buena cantidad de algoritmos, pero... ¿cómo saber cuál
es el que necesitas? ¿cuál es EL algoritmo?

Cada algoritmo se comporta de modo diferente de acuerdo a la cantidad y la
forma en que se le presenten los datos, entre otras cosas. No existe EL
algoritmo de ordenamiento. Sólo existe el mejor para cada caso particular. Debes
conocer a fondo el problema que quieres resolver, y aplicar el más adecuado.
Aunque hay algunas preguntas que te pueden ayudar a elegir:

¿Qué grado de orden tendrá la información que vas a manejar?
Si la información va a estar casi ordenada y no quieres complicarte, un
algoritmo sencillo como el ordenamiento burbuja será suficiente. Si por el
contrario los datos van a estar muy desordenados, un algoritmo poderoso como
Quicksort puede ser el más indicado. Y si no puedes hacer una presunción sobre
el grado de orden de la información, lo mejor será elegir un algoritmo que se
comporte de manera similar en cualquiera de estos dos casos extremos.

¿Qué cantidad de datos vas a manipular? Si la cantidad es
pequeña, no es necesario utilizar un algoritmo complejo, y es preferible uno
de fácil implementación. Una cantidad muy grande puede hacer prohibitivo
utilizar un algoritmo que requiera de mucha memoria adicional.

¿Qué tipo de datos quieres ordenar? Algunos algoritmos sólo
funcionan con un tipo específico de datos (enteros, enteros positivos, etc.) y
otros son generales, es decir, aplicables a cualquier tipo de dato.

¿Qué tamaño tienen los registros de tu lista? Algunos
algoritmos realizan múltiples intercambios (burbuja, inserción). Si los
registros son de gran tamaño estos intercambios son más lentos.

5. Demostración y Código Fuente.

Puedes descargar dos programas de demostración con los algoritmos presentados
en este artículo:

OrdWin: En este
programa puedes ver una demostración gráfica de cada algoritmo. También puedes
experimentar ordenando listas de la longitud que quieras, observando el tiempo
que demoran, la cantidad de comparaciones y de intercambios que realizan. Fue
creado utilizando el compilador LccWin32 de Jacob Navia, pero
el fichero descargable es un proyecto para Dev-C++. Incluye el ejecutable, el
código fuente y este artículo completo.

Ordenar: Este
programa es más indicado si lo que quieres es mirar código. No hay funciones
gráficas ni nada del API de Windows. Debería funcionar en cualquier otro
compilador sin mayores cambios, pues está hecho en ANSI C. Fue probado con éxito
en Turbo C++, DJGPP, LccWin32, y Dev-C++. Quedó bastante feo, pero es el precio
que hay que pagar por la portabilidad ;-). Sólo incluye el código.

6. Algunas palabras para terminar.

No sabía si escribir este artículo o no. Probablemente no sea yo el indicado
para hacerlo. Después de todo no soy ningún experto ni mucho menos, pero creo
que puede ayudar a alguien que sepa menos que yo (no deben ser muchos :-)). Por
eso pido tu colaboración para mejorar este documento y hacerlo algo útil. Si
tienes sugerencias, comentarios o correcciones por favor házmelo saber.

7. Bibliografía.

H.M. Deitel, P.J. Deitel: "Cómo programar en C/C++".
Editorial Prentice Hall.

Charles Bowman: "Algoritmos y estructuras de datos: Aproximación en
C". Oxford University Press, 1999.

"Dictionary of Algorithms, Data
Structures, and Problems"

[C con Clase] [Artículos] [1 Burbuja]

© Diciembre de 2001 - Julián Hidalgo