Algoritmos de Ordenamiento

[C con Clase] [Artículos] [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:

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:

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:

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:

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.

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


©2001 - Julián Hidalgo