Algoritmo de clasificación
En ciencias de la computación , un algoritmo de ordenación es un algoritmo que pone de elementos de una lista en un orden . Los órdenes más utilizados son el orden numérico y el orden lexicográfico , ascendente o descendente. La clasificación eficiente es importante para optimizar la eficiencia de otros algoritmos (como los de búsqueda y combinación ) que requieren que los datos de entrada estén en listas ordenadas. La clasificación también suele ser útil para canonicalizar datos y producir resultados legibles por humanos.
Para una eficiencia óptima, los datos de entrada deben almacenarse en una estructura de datos que permita el acceso aleatorio en lugar de una que solo permita el acceso secuencial .
Desde el comienzo de la informática, el problema de clasificación ha atraído una gran cantidad de investigación, quizás debido a la complejidad de resolverlo de manera eficiente a pesar de su simple y familiar declaración. Entre los autores de los primeros algoritmos de clasificación alrededor de 1951 se encontraba Betty Holberton , quien trabajó en ENIAC y UNIVAC . [1] [2] La clasificación de burbujas se analizó ya en 1956. [3] Los algoritmos óptimos asintóticamente se conocen desde mediados del siglo XX; todavía se están inventando nuevos algoritmos, con el Timsort ampliamente utilizado que data de 2002, y la biblioteca sort se publicó por primera vez en 2006.
Los algoritmos de ordenación por comparación tienen un requisito fundamental de comparaciones Ω ( n log n ) (algunas secuencias de entrada requerirán un múltiplo de n log n comparaciones, donde n es el número de elementos en la matriz que se ordenarán). Los algoritmos que no se basan en comparaciones, como el ordenamiento por recuento , pueden tener un mejor rendimiento.
Los algoritmos de clasificación prevalecen en las clases de introducción a la informática , donde la abundancia de algoritmos para el problema proporciona una introducción suave a una variedad de conceptos de algoritmos centrales, como la notación O grande , algoritmos de división y conquista , estructuras de datos como montones y árboles binarios , algoritmos aleatorios , mejor, peor y promedio caso de análisis, las compensaciones de tiempo-espacio y límites superior e inferior .
La clasificación de arreglos pequeños de manera óptima (en la menor cantidad de comparaciones e intercambios) o rápida (es decir, teniendo en cuenta los detalles específicos de la máquina) sigue siendo un problema de investigación abierto, con soluciones que solo se conocen para arreglos muy pequeños (<20 elementos). De manera similar, la clasificación óptima (según varias definiciones) en una máquina paralela es un tema de investigación abierto.
