Me había propuesto un post largo sobre este tema pero siguiendo la máxima «no reinventes la rueda» he decidido hacer un artículo más chico y recomendaros encarecidamente el sitio web Sorting Algorithms en su lugar. Aquí, no sólo encontrareis los métodos de ordenación más comunes sino que además contreis con animaciones, pseudocódigo, complejidad, comparativa… Qué más se puede pedir.
La ordenación de elementos es uno de los primeros problemas que pueden verse en la ingeniería informática. Involucra muchos conceptos importantes como el buen orden, la notción O, casos medio, mejor y peor, etc
Empezaremos por definir el orden de una lista de elementos diciendo:
Una lista está ordenada si sus elementos están en orden creciente sin importarnos si dos elementos son iguales.
Ahora vamos a definir escuétamente algunas características importantes de clasificación:
- Complejidad. Quizá la más importante. Se refiere al tiempo empleado en completar la ordenacion. En principio se considera un buen tiempo aquellos pertenecientes a O(n log n) y malos, a los pertenecientes a O(n^2). De nuevo es importante aquí la notación O. Se deben considerar los casos mejor, peor y medio.
- Uso de memoria. A parte de lo que ocupe la lista, cuánto espacio extra se necesita para ejecutar el algoritmo. Realmente es otra medida de complejidad así que seguiremos utilizando la notación O para cuantificarlo.
- Adaptabilidad. Si la list que nos dan YA está ordenada, entonces el algoritmo de ordenación debería tardar menos (a fin de cuentas tendrá que comprobarla pero no reordenarla) pero esto no siempre es así. Un algoritmo de ordenación es adaptable si adapta su ejecución al estado actual de la lista.
Otras medidas que suelen aportarse es su complejidad computacional (el número de operaciones como comparaciones o cambios) y la estabilidad (imagina que ordenas pares (X, Y) por el primer elemento del par; se trata de la capacidad de mantener dos pares con el mismo primer elemento en el mismo orden que en la lista original).
Uno + uno = diez 