En informática , un algoritmo de clasificación es un algoritmo que ordena los elementos de una lista . Los órdenes más utilizados son el orden numérico y el orden lexicográfico , ya sea ascendente o descendente. La clasificación eficiente es importante para optimizar la eficiencia de otros algoritmos (como los algoritmos 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.
Formalmente, la salida de cualquier algoritmo de clasificación debe cumplir dos condiciones:
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 los inicios de la informática, el problema de la clasificación ha atraído una gran cantidad de investigaciones, tal vez debido a la complejidad de resolverlo de manera eficiente a pesar de su planteamiento simple y familiar. Entre los autores de los primeros algoritmos de clasificación alrededor de 1951 se encontraba Betty Holberton , que trabajó en ENIAC y UNIVAC . [1] [2] La clasificación de burbujas se analizó ya en 1956. [3] Los algoritmos asintóticamente óptimos se conocen desde mediados del siglo XX; todavía se están inventando nuevos algoritmos; el ampliamente utilizado Timsort data de 2002, y la biblioteca sort se publicó por primera vez en 2006.
Los algoritmos de clasificació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 de la matriz que se van a ordenar). Los algoritmos que no se basan en comparaciones, como la clasificación por conteo , 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 suave introducción a una variedad de conceptos básicos de algoritmos, como la notación O grande , los algoritmos de divide y vencerás , las estructuras de datos como los montones y los binarios. árboles , algoritmos aleatorios , análisis de casos mejor, peor y promedio , compensaciones espacio-temporales y límites superior e inferior .
Clasificar arreglos pequeños de manera óptima (en la menor cantidad de comparaciones e intercambios) o rápido (es decir, teniendo en cuenta detalles específicos de la máquina) sigue siendo un problema de investigación abierto, y las soluciones 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.
Los algoritmos de clasificación se pueden clasificar por:
Los algoritmos de clasificación estables clasifican elementos iguales en el mismo orden en que aparecen en la entrada. Por ejemplo, en el ejemplo de clasificación de cartas de la derecha, las cartas se clasifican por su rango y se ignora su palo. Esto permite la posibilidad de múltiples versiones diferentes ordenadas correctamente de la lista original. Los algoritmos de clasificación estable eligen uno de estos, de acuerdo con la siguiente regla: si dos elementos se comparan como iguales (como las dos cartas de 5), entonces se conservará su orden relativo, es decir, si uno aparece antes que el otro en la entrada, aparecerá antes que el otro en la salida.
La estabilidad es importante para preservar el orden en múltiples clasificaciones del mismo conjunto de datos . Por ejemplo, supongamos que los registros de estudiantes que constan de nombre y sección de clase se ordenan dinámicamente, primero por nombre y luego por sección de clase. Si se utiliza un algoritmo de clasificación estable en ambos casos, la operación de clasificación por sección de clase no cambiará el orden de los nombres; con una clasificación inestable, podría ser que la clasificación por sección mezcle el orden de los nombres, lo que da como resultado una lista no alfabética de estudiantes.
De manera más formal, los datos que se clasifican se pueden representar como un registro o una tupla de valores, y la parte de los datos que se utiliza para ordenar se denomina clave . En el ejemplo de las cartas, las cartas se representan como un registro (rango, palo) y la clave es el rango. Un algoritmo de clasificación es estable si siempre que hay dos registros R y S con la misma clave, y R aparece antes de S en la lista original, entonces R siempre aparecerá antes de S en la lista ordenada.
Cuando elementos iguales son indistinguibles, como ocurre con los números enteros o, más generalmente, cualquier dato donde el elemento completo es la clave, la estabilidad no es un problema. La estabilidad tampoco es un problema si todas las claves son diferentes.
Los algoritmos de clasificación inestables se pueden implementar especialmente para que sean estables. Una forma de hacerlo es ampliar artificialmente la comparación de claves, de modo que las comparaciones entre dos objetos con claves iguales se decidan utilizando el orden de las entradas en la lista de entrada original como criterio de desempate. Sin embargo, recordar este orden puede requerir tiempo y espacio adicionales.
Una aplicación para algoritmos de clasificación estables es ordenar una lista utilizando una clave primaria y secundaria. Por ejemplo, supongamos que deseamos ordenar una mano de cartas de modo que los palos estén en el orden tréboles (♣), diamantes ( ♦ ), corazones ( ♥ ), picas (♠) y, dentro de cada palo, las cartas estén ordenadas por rango. Esto se puede hacer clasificando primero las cartas por rango (usando cualquier tipo) y luego haciendo una clasificación estable por palo:
Dentro de cada palo, la clasificación estable conserva el orden por rango que ya se realizó. Esta idea se puede extender a cualquier número de claves y se utiliza mediante clasificación por base . Se puede lograr el mismo efecto con una clasificación inestable utilizando una comparación de claves lexicográficas, que, por ejemplo, compara primero por palo y luego por rango si los palos son iguales.
En estas tablas, n es el número de registros que se ordenarán. Las columnas "Mejor", "Promedio" y "Peor" dan la complejidad temporal en cada caso, bajo el supuesto de que la longitud de cada clave es constante y, por lo tanto, que todas las comparaciones, intercambios y otras operaciones pueden realizarse en un tiempo constante. "Memoria" denota la cantidad de almacenamiento adicional necesario además del utilizado por la propia lista, bajo el mismo supuesto. Los tiempos de ejecución y los requisitos de memoria enumerados están dentro de la notación O grande , por lo que la base de los logaritmos no importa. La notación log 2 n significa (log n ) 2 .
A continuación se muestra una tabla de tipos de comparación . Una clasificación por comparación no puede funcionar mejor que O ( n log n ) en promedio. [4]
La siguiente tabla describe algoritmos de clasificación de números enteros y otros algoritmos de clasificación que no son clasificaciones de comparación . Como tales, no se limitan a Ω ( n log n ) . [12] Las complejidades siguientes suponen que se ordenarán n elementos, con claves de tamaño k , tamaño de dígito d y r el rango de números que se ordenarán. Muchos de ellos se basan en el supuesto de que el tamaño de la clave es lo suficientemente grande como para que todas las entradas tengan valores de clave únicos y, por lo tanto, n ≪ 2 k , donde ≪ significa "mucho menor que". En el modelo de máquina de acceso aleatorio de costo unitario , los algoritmos con un tiempo de ejecución de , como la clasificación por base, todavía toman un tiempo proporcional a Θ( n log n ) , porque n está limitado a no ser mayor que , y un número mayor de elementos. ordenar requeriría una k mayor para almacenarlos en la memoria. [13]
Samplesort se puede utilizar para paralelizar cualquiera de los tipos que no son de comparación, distribuyendo datos de manera eficiente en varios depósitos y luego transmitiendo la clasificación a varios procesadores, sin necesidad de fusionarlos, ya que los depósitos ya están ordenados entre sí.
Algunos algoritmos son lentos en comparación con los discutidos anteriormente, como el bogosort con tiempo de ejecución ilimitado y el stooge sort que tiene O ( n 2.7 ) tiempo de ejecución. Estos tipos generalmente se describen con fines educativos para demostrar cómo se estima el tiempo de ejecución de los algoritmos. La siguiente tabla describe algunos algoritmos de clasificación que no son prácticos para el uso en la vida real en contextos de software tradicionales debido a un rendimiento extremadamente pobre o requisitos de hardware especializados.
Los informáticos teóricos han detallado otros algoritmos de clasificación que proporcionan una complejidad de tiempo mejor que O ( n log n ) asumiendo restricciones adicionales, que incluyen:
Si bien existe una gran cantidad de algoritmos de clasificación, en las implementaciones prácticas predominan unos pocos algoritmos. La ordenación por inserción se usa ampliamente para conjuntos de datos pequeños, mientras que para conjuntos de datos grandes se usa una ordenación asintóticamente eficiente, principalmente ordenación en montón, ordenación por fusión o ordenación rápida. Las implementaciones eficientes generalmente utilizan un algoritmo híbrido , que combina un algoritmo asintóticamente eficiente para la clasificación general con clasificación por inserción para listas pequeñas al final de una recursividad. Las implementaciones altamente ajustadas utilizan variantes más sofisticadas, como Timsort (ordenación por combinación, ordenación por inserción y lógica adicional), que se usa en Android , Java y Python , e introsort (clasificación rápida y heapsort), que se usa (en formas variantes) en alguna clasificación de C++. implementaciones y en .NET .
Para datos más restringidos, como números en un intervalo fijo, se utilizan ampliamente clasificaciones de distribución como la clasificación por conteo o la clasificación por base. La clasificación de burbujas y sus variantes rara vez se utilizan en la práctica, pero se encuentran comúnmente en la enseñanza y en los debates teóricos.
Al clasificar físicamente objetos (como alfabetizar trabajos, exámenes o libros), las personas generalmente usan intuitivamente la clasificación por inserción para conjuntos pequeños. Para conjuntos más grandes, la gente suele clasificar primero, por ejemplo, por letra inicial, y el agrupamiento múltiple permite una clasificación práctica de conjuntos muy grandes. A menudo el espacio es relativamente barato, como por ejemplo esparcir objetos en el suelo o en un área grande, pero las operaciones son costosas, particularmente mover un objeto a gran distancia; la localidad de referencia es importante. Las clasificaciones por combinación también son prácticas para objetos físicos, particularmente porque se pueden usar dos manos, una para cada lista a fusionar, mientras que otros algoritmos, como la clasificación en montón o la clasificación rápida, no son adecuados para el uso humano. Otros algoritmos, como la clasificación de biblioteca , una variante de la clasificación por inserción que deja espacios, también son prácticos para uso físico.
Dos de los tipos más simples son el ordenamiento por inserción y el ordenamiento por selección, los cuales son eficientes en datos pequeños, debido a su baja sobrecarga, pero no eficientes en datos grandes. La ordenación por inserción es generalmente más rápida que la ordenación por selección en la práctica, debido a menos comparaciones y un buen rendimiento en datos casi ordenados y, por lo tanto, se prefiere en la práctica, pero la ordenación por selección utiliza menos escrituras y, por lo tanto, se usa cuando el rendimiento de escritura es un factor limitante.
La clasificación por inserción es un algoritmo de clasificación simple que es relativamente eficiente para listas pequeñas y listas en su mayoría ordenadas, y a menudo se usa como parte de algoritmos más sofisticados. Funciona tomando elementos de la lista uno por uno e insertándolos en su posición correcta en una nueva lista ordenada similar a cómo uno pone dinero en su billetera. [22] En las matrices, la nueva lista y los elementos restantes pueden compartir el espacio de la matriz, pero la inserción es costosa y requiere desplazar todos los elementos siguientes uno por uno. Shellsort es una variante del ordenamiento por inserción que es más eficiente para listas más grandes.
La clasificación por selección es una clasificación por comparación in situ . Tiene complejidad O ( n 2 ), lo que lo hace ineficiente en listas grandes y, en general, funciona peor que el tipo de inserción similar . La clasificación por selección destaca por su simplicidad y también tiene ventajas de rendimiento sobre algoritmos más complicados en determinadas situaciones.
El algoritmo encuentra el valor mínimo, lo intercambia con el valor de la primera posición y repite estos pasos durante el resto de la lista. [23] No realiza más de n intercambios y, por lo tanto, es útil cuando el intercambio es muy costoso.
Los algoritmos de clasificación generales prácticos casi siempre se basan en un algoritmo con una complejidad de tiempo promedio (y generalmente en el peor de los casos) O ( n log n ), de los cuales los más comunes son la clasificación en montón, la clasificación por fusión y la clasificación rápida. Cada uno tiene ventajas e inconvenientes, siendo el más significativo que la implementación simple de ordenación por fusión usa O( n ) espacio adicional, y la implementación simple de ordenación rápida tiene O( n 2 ) complejidad en el peor de los casos. Estos problemas pueden resolverse o mejorarse a costa de un algoritmo más complejo.
Si bien estos algoritmos son asintóticamente eficientes con datos aleatorios, para lograr una eficiencia práctica con datos del mundo real se utilizan varias modificaciones. En primer lugar, la sobrecarga de estos algoritmos se vuelve significativa en datos más pequeños, por lo que a menudo se utiliza un algoritmo híbrido, que comúnmente cambia a ordenación por inserción una vez que los datos son lo suficientemente pequeños. En segundo lugar, los algoritmos a menudo funcionan mal en datos ya ordenados o casi ordenados; estos son comunes en los datos del mundo real y pueden ordenarse en O( n ) tiempo mediante algoritmos apropiados. Finalmente, también pueden ser inestables , y la estabilidad es a menudo una propiedad deseable en cierto modo. Por lo tanto, a menudo se emplean algoritmos más sofisticados, como Timsort (basado en ordenación por fusión) o introsort (basado en ordenación rápida, recurriendo a ordenación en montón).
Merge sort aprovecha la facilidad de fusionar listas ya ordenadas en una nueva lista ordenada. Comienza comparando cada dos elementos (es decir, 1 con 2, luego 3 con 4...) e intercambiándolos si el primero debe ir después del segundo. Luego fusiona cada una de las listas resultantes de dos en listas de cuatro, luego fusiona esas listas de cuatro, y así sucesivamente; hasta que al menos dos listas se fusionen en la lista ordenada final. [24] De los algoritmos descritos aquí, este es el primero que se escala bien a listas muy grandes, porque su tiempo de ejecución en el peor de los casos es O ( n log n ). También se aplica fácilmente a listas, no solo a matrices, ya que solo requiere acceso secuencial, no aleatorio. Sin embargo, tiene una complejidad espacial O ( n ) adicional e implica una gran cantidad de copias en implementaciones simples.
La ordenación por combinación ha experimentado un aumento relativamente reciente en popularidad para implementaciones prácticas, debido a su uso en el sofisticado algoritmo Timsort , que se utiliza para la rutina de ordenación estándar en los lenguajes de programación Python [25] y Java (a partir de JDK7 [26] ). . La clasificación por fusión en sí es la rutina estándar en Perl , [27] entre otros, y se ha utilizado en Java al menos desde 2000 en JDK1.3 . [28]
Heapsort es una versión mucho más eficiente de la clasificación por selección . También funciona determinando el elemento más grande (o más pequeño) de la lista, colocándolo al final (o al principio) de la lista y luego continúa con el resto de la lista, pero logra esta tarea de manera eficiente mediante el uso de una estructura de datos llamada montón , un tipo especial de árbol binario . [29] Una vez que la lista de datos se ha convertido en un montón, se garantiza que el nodo raíz será el elemento más grande (o más pequeño). Cuando se elimina y se coloca al final de la lista, el montón se reorganiza de modo que el elemento más grande restante se mueva a la raíz. Usando el montón, encontrar el siguiente elemento más grande lleva O(log n ) tiempo, en lugar de O( n ) para un escaneo lineal como en la clasificación por selección simple. Esto permite que Heapsort se ejecute en un tiempo O ( n log n ), y este también es el peor de los casos de complejidad.
Quicksort es un algoritmo de divide y vencerás que se basa en una operación de partición : para particionar una matriz, se selecciona un elemento llamado pivote . [30] [31] Todos los elementos más pequeños que el pivote se mueven antes y todos los elementos mayores se mueven después. Esto se puede hacer de manera eficiente en tiempo lineal y en el lugar . Luego, las sublistas menores y mayores se ordenan de forma recursiva. Esto produce una complejidad de tiempo promedio de O ( n log n ), con una sobrecarga baja y, por lo tanto, este es un algoritmo popular. Las implementaciones eficientes de clasificación rápida (con partición in situ) suelen ser clasificaciones inestables y algo complejas, pero se encuentran entre los algoritmos de clasificación más rápidos en la práctica. Junto con su modesto uso de espacio O(log n ), Quicksort es uno de los algoritmos de clasificación más populares y está disponible en muchas bibliotecas de programación estándar.
La advertencia importante sobre la ordenación rápida es que su desempeño en el peor de los casos es O( n 2 ); Si bien esto es poco común, en implementaciones ingenuas (eligiendo el primer o último elemento como pivote) esto ocurre con datos ordenados, lo cual es un caso común. Por lo tanto, la cuestión más compleja en la clasificación rápida es elegir un buen elemento de pivote, ya que las malas elecciones de pivotes pueden dar como resultado un rendimiento O( n 2 ) drásticamente más lento , pero una buena elección de pivotes produce un rendimiento O( n log n ), que es asintóticamente óptimo. . Por ejemplo, si en cada paso se elige la mediana como pivote, entonces el algoritmo funciona en O ( n log n ). Sin embargo, encontrar la mediana, por ejemplo mediante el algoritmo de selección de mediana de medianas, es una operación O( n ) en listas no ordenadas y, por lo tanto, exige una sobrecarga significativa con la clasificación. En la práctica, elegir un pivote aleatorio casi con seguridad produce un rendimiento O( n log n ).
Si una garantía de rendimiento O( n log n ) es importante, existe una modificación simple para lograrlo. La idea, debida a Musser, es establecer un límite a la profundidad máxima de recursividad. [32] Si se excede ese límite, la clasificación continúa utilizando el algoritmo heapsort. Musser propuso que el límite debería ser , que es aproximadamente el doble de la profundidad máxima de recursión que uno esperaría en promedio con una matriz ordenada aleatoriamente.
Shellsort fue inventado por Donald Shell en 1959. [33] Mejora la clasificación por inserción moviendo elementos fuera de orden más de una posición a la vez. El concepto detrás de Shellsort es que la ordenación por inserción se realiza en el tiempo, donde k es la mayor distancia entre dos elementos fuera de lugar. Esto significa que, en general, funcionan en O ( n 2 ), pero para los datos que están mayormente ordenados, con solo unos pocos elementos fuera de lugar, funcionan más rápido. Entonces, al ordenar primero los elementos que están lejos y reducir progresivamente la brecha entre los elementos a ordenar, la clasificación final se calcula mucho más rápido. Una implementación se puede describir como organizar la secuencia de datos en una matriz bidimensional y luego ordenar las columnas de la matriz mediante ordenación por inserción.
La complejidad temporal del peor de los casos de Shellsort es un problema abierto y depende de la secuencia de espacios utilizada, con complejidades conocidas que van desde O ( n 2 ) hasta O ( n 4/3 ) y Θ ( n log 2 n ). Esto, combinado con el hecho de que Shellsort está in situ , solo necesita una cantidad relativamente pequeña de código y no requiere el uso de la pila de llamadas , lo hace útil en situaciones donde la memoria es escasa, como en sistemas integrados . y núcleos del sistema operativo .
La clasificación de burbujas y variantes como la clasificación de peine y la clasificación de cóctel son algoritmos de clasificación simples y altamente ineficientes. Se ven con frecuencia en textos introductorios debido a su facilidad de análisis, pero rara vez se utilizan en la práctica.
La clasificación de burbujas es un algoritmo de clasificación simple. El algoritmo comienza al principio del conjunto de datos. Compara los dos primeros elementos y, si el primero es mayor que el segundo, los intercambia. Continúa haciendo esto para cada par de elementos adyacentes hasta el final del conjunto de datos. Luego comienza de nuevo con los dos primeros elementos, repitiendo hasta que no se hayan producido cambios en la última pasada. [34] El tiempo promedio de este algoritmo y el rendimiento en el peor de los casos es O ( n 2 ), por lo que rara vez se utiliza para ordenar conjuntos de datos grandes y desordenados. La clasificación por burbujas se puede utilizar para clasificar una pequeña cantidad de elementos (donde su ineficiencia asintótica no es una penalización alta). La ordenación por burbujas también se puede utilizar eficientemente en una lista de cualquier longitud que esté casi ordenada (es decir, los elementos no estén significativamente fuera de lugar). Por ejemplo, si algún número de elementos están fuera de lugar en una sola posición (por ejemplo, 0123546789 y 1032547698), el intercambio de clasificación de burbujas los pondrá en orden en la primera pasada, la segunda pasada encontrará todos los elementos en orden, por lo que la clasificación toma solo 2 n tiempo.
[35]
La clasificación en peine es un algoritmo de clasificación relativamente simple basado en la clasificación por burbujas y diseñado originalmente por Włodzimierz Dobosiewicz en 1980. [36] Posteriormente fue redescubierto y popularizado por Stephen Lacey y Richard Box con un artículo de la revista Byte publicado en abril de 1991. La idea básica es para eliminar tortugas , o valores pequeños cerca del final de la lista, ya que en una clasificación de burbujas estos ralentizan enormemente la clasificación. ( Los conejos , valores grandes alrededor del comienzo de la lista, no plantean un problema en la clasificación de burbujas). Lo logra intercambiando inicialmente elementos que están a cierta distancia entre sí en la matriz, en lugar de intercambiar solo elementos si son adyacentes a entre sí, y luego reduciendo la distancia elegida hasta que funcione como una especie de burbuja normal. Por lo tanto, si se puede pensar en Shellsort como una versión generalizada de la ordenación por inserción que intercambia elementos espaciados a cierta distancia entre sí, la ordenación en peine se puede considerar como la misma generalización aplicada a la ordenación por burbujas.
La clasificación de intercambio a veces se confunde con la clasificación de burbujas, aunque en realidad los algoritmos son distintos. [37] [38] La clasificación por intercambio funciona comparando el primer elemento con todos los elementos superiores, intercambiándolos cuando sea necesario, garantizando así que el primer elemento sea correcto para el orden de clasificación final; luego procede a hacer lo mismo con el segundo elemento, y así sucesivamente. Carece de la ventaja que tiene la clasificación por burbujas de detectar en una sola pasada si la lista ya está ordenada, pero puede ser más rápido que la clasificación por burbujas por un factor constante (una pasada menos sobre los datos a ordenar; la mitad de comparaciones totales) en peores situaciones. Como cualquier ordenación O( n 2 ) simple, puede ser razonablemente rápida en conjuntos de datos muy pequeños, aunque en general la ordenación por inserción será más rápida.
La clasificación por distribución se refiere a cualquier algoritmo de clasificación en el que los datos se distribuyen desde su entrada a múltiples estructuras intermedias que luego se recopilan y colocan en la salida. Por ejemplo, tanto la clasificación por cubos como la clasificación flash son algoritmos de clasificación basados en distribución. Los algoritmos de clasificación de distribución se pueden usar en un solo procesador o pueden ser un algoritmo distribuido , donde los subconjuntos individuales se clasifican por separado en diferentes procesadores y luego se combinan. Esto permite la clasificación externa de datos demasiado grandes para caber en la memoria de una sola computadora.
La clasificación por conteo es aplicable cuando se sabe que cada entrada pertenece a un conjunto particular, S , de posibilidades. El algoritmo se ejecuta en tiempo O(| S | + n ) y en memoria O(| S |) donde n es la longitud de la entrada. Funciona creando una matriz de números enteros de tamaño | S | y usar el i ésimo contenedor para contar las apariciones del i ésimo miembro de S en la entrada. Luego, cada entrada se cuenta incrementando el valor de su contenedor correspondiente. Luego, se recorre la matriz de conteo para organizar todas las entradas en orden. Este algoritmo de clasificación a menudo no se puede utilizar porque S necesita ser razonablemente pequeño para que el algoritmo sea eficiente, pero es extremadamente rápido y demuestra un gran comportamiento asintótico a medida que n aumenta. También se puede modificar para proporcionar un comportamiento estable.
La clasificación por depósitos es un algoritmo de clasificación de divide y vencerás que generaliza la clasificación por conteo dividiendo una matriz en un número finito de depósitos. Luego, cada depósito se clasifica individualmente, ya sea utilizando un algoritmo de clasificación diferente o aplicando recursivamente el algoritmo de clasificación de depósitos.
Una clasificación de depósitos funciona mejor cuando los elementos del conjunto de datos se distribuyen uniformemente en todos los depósitos.
Radix sort es un algoritmo que clasifica números procesando dígitos individuales. n números que constan de k dígitos cada uno se ordenan en tiempo O( n · k ). La clasificación Radix puede procesar dígitos de cada número, ya sea comenzando desde el dígito menos significativo (LSD) o desde el dígito más significativo (MSD). El algoritmo LSD primero ordena la lista por el dígito menos significativo preservando su orden relativo mediante una clasificación estable. Luego los clasifica por el siguiente dígito, y así sucesivamente desde el menos significativo al más significativo, terminando con una lista ordenada. Mientras que la clasificación por base LSD requiere el uso de una clasificación estable, el algoritmo de clasificación por base MSD no lo requiere (a menos que se desee una clasificación estable). La clasificación de bases MSD local no es estable. Es común que el algoritmo de clasificación por conteo sea utilizado internamente por la clasificación por base. Un enfoque de clasificación híbrido , como el uso de clasificación por inserción para contenedores pequeños, mejora significativamente el rendimiento de la clasificación por base.
Cuando el tamaño de la matriz a ordenar se acerca o excede la memoria primaria disponible, de modo que se debe emplear un disco (mucho más lento) o espacio de intercambio, el patrón de uso de memoria de un algoritmo de clasificación se vuelve importante, y un algoritmo que podría haber sido bastante eficiente cuando la matriz cabe fácilmente en la RAM puede resultar poco práctica. En este escenario, el número total de comparaciones se vuelve (relativamente) menos importante, y el número de veces que se deben copiar o intercambiar secciones de memoria hacia y desde el disco puede dominar las características de rendimiento de un algoritmo. Por lo tanto, el número de pasadas y la localización de las comparaciones pueden ser más importantes que el número bruto de comparaciones, ya que las comparaciones de elementos cercanos entre sí ocurren a la velocidad del bus del sistema (o, con el almacenamiento en caché, incluso a la velocidad de la CPU ), lo que, en comparación a la velocidad del disco, es prácticamente instantáneo.
Por ejemplo, el popular algoritmo recursivo de ordenación rápida proporciona un rendimiento bastante razonable con RAM adecuada, pero debido a la forma recursiva en la que copia partes de la matriz, se vuelve mucho menos práctico cuando la matriz no cabe en la RAM, porque puede causar una serie de errores. operaciones de copia o movimiento lentas hacia y desde el disco. En ese escenario, puede ser preferible otro algoritmo incluso si requiere más comparaciones totales.
Una forma de solucionar este problema, que funciona bien cuando se ordenan registros complejos (como en una base de datos relacional ) por un campo clave relativamente pequeño, es crear un índice en la matriz y luego ordenar el índice, en lugar de todo el índice. formación. (Luego se puede producir una versión ordenada de toda la matriz con una sola pasada, leyendo el índice, pero a menudo incluso eso es innecesario, ya que tener el índice ordenado es adecuado). Debido a que el índice es mucho más pequeño que la matriz completa, puede caben fácilmente en la memoria donde no cabría toda la matriz, eliminando efectivamente el problema del intercambio de discos. Este procedimiento a veces se denomina "clasificación de etiquetas". [39]
Otra técnica para superar el problema del tamaño de la memoria es utilizar la clasificación externa ; por ejemplo, una de las formas es combinar dos algoritmos de una manera que aproveche la fuerza de cada uno para mejorar el rendimiento general. Por ejemplo, la matriz podría subdividirse en fragmentos de un tamaño que quepa en la RAM, ordenar el contenido de cada fragmento mediante un algoritmo eficiente (como Quicksort ) y fusionar los resultados mediante una combinación de k vías similar a la utilizada en fusionar ordenación . Esto es más rápido que realizar una clasificación por combinación o una clasificación rápida en toda la lista. [40] [41]
También se pueden combinar técnicas. Para ordenar conjuntos de datos muy grandes que exceden ampliamente la memoria del sistema, es posible que incluso el índice deba ordenarse utilizando un algoritmo o una combinación de algoritmos diseñados para funcionar razonablemente con la memoria virtual , es decir, para reducir la cantidad de intercambio requerido.
Los problemas relacionados incluyen ordenación aproximada (ordenar una secuencia dentro de una cierta cantidad del orden correcto), ordenación parcial (ordenar sólo los k elementos más pequeños de una lista, o encontrar los k elementos más pequeños, pero desordenados) y selección (calcular el k ésimo elemento más pequeño). Estos pueden resolverse de manera ineficiente mediante una clasificación total, pero existen algoritmos más eficientes, a menudo derivados de la generalización de un algoritmo de clasificación. El ejemplo más notable es la selección rápida , que está relacionada con la ordenación rápida . Por el contrario, algunos algoritmos de clasificación pueden derivarse mediante la aplicación repetida de un algoritmo de selección; La ordenación rápida y la selección rápida pueden verse como el mismo movimiento de pivote, diferenciándose solo en si se recurre en ambos lados (clasificación rápida, divide y vencerás ) o en un lado (selección rápida, disminuye y vencerás ).
Una especie de opuesto a un algoritmo de clasificación es un algoritmo de barajado . Estos son fundamentalmente diferentes porque requieren una fuente de números aleatorios. La mezcla también se puede implementar mediante un algoritmo de clasificación, es decir, mediante una clasificación aleatoria: asignar un número aleatorio a cada elemento de la lista y luego ordenar según los números aleatorios. Sin embargo, esto generalmente no se hace en la práctica y existe un algoritmo simple y eficiente bien conocido para barajar: el barajado de Fisher-Yates .
Los algoritmos de clasificación son ineficaces para encontrar un orden en muchas situaciones. Por lo general, cuando los elementos no tienen una función de comparación confiable (preferencias colaborativas como los sistemas de votación ), las comparaciones son muy costosas ( deportes ), o cuando sería imposible comparar por pares todos los elementos para todos los criterios ( motores de búsqueda ). En estos casos, el problema suele denominarse clasificación y el objetivo es encontrar el "mejor" resultado para algunos criterios según probabilidades inferidas de comparaciones o clasificaciones. Un ejemplo común es el ajedrez, donde los jugadores se clasifican según el sistema de clasificación Elo y las clasificaciones se determinan mediante un sistema de torneos en lugar de un algoritmo de clasificación.
