Análisis y Diseño de Algoritmos

Prof: Ing. Victor Garro

Asistente: Marco Elizondo Vargas

ORDENAMIENTOS

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.

Tabla comparativa de algoritmos
Nombre	Complejidad	Estabilidad	Memoria adicional
Ordenamiento Burbuja (Bubblesort)	O(n²)	Estable	No
Ordenamiento por Selección	O(n²)	No Estable	No
Ordenamiento por Inserción	O(n²)	Estable	No
Ordenamiento Rápido (Quicksort)	O(n * log₂(n))	No Estable	No

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.