En informática , un algoritmo de clasificación es un algoritmo que pone los elementos de una lista en un orden determinado . Los órdenes más utilizados son el orden numérico y el orden lexicográfico . 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. Más formalmente, la salida de cualquier algoritmo de clasificación debe satisfacer dos condiciones:
- La salida está en orden no decreciente (cada elemento no es más pequeño que el elemento anterior según el orden total deseado );
- La salida es una permutación (un reordenamiento, pero conservando todos los elementos originales) de la entrada.
Para una eficiencia óptima, los datos de entrada en la memoria rápida deben almacenarse en una estructura de datos que permita el acceso aleatorio en lugar de una que solo permita el acceso secuencial .
Los algoritmos de clasificación a menudo se conocen como una palabra seguida de la palabra "ordenar" y gramaticalmente se usan en inglés como frases nominales, por ejemplo, en la oración, "es ineficaz usar la ordenación por inserción en listas grandes" a la que se refiere la clasificación por inserción de frase el algoritmo de clasificación de clasificación por inserción .
Historia
Desde el comienzo de la informática, el problema de clasificación ha atraído una gran cantidad de investigación, tal vez debido a la complejidad de resolverlo de manera eficiente a pesar de su declaración simple y familiar. Entre los autores de los primeros algoritmos de clasificación alrededor de 1951 se encontraba Betty Holberton (nacida Snyder), que trabajó en ENIAC y UNIVAC . [1] [2] La clasificación de burbujas se analizó ya en 1956. [3] Los algoritmos de clasificación de 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 ordenarán). Los algoritmos que no se basan en comparaciones, como el ordenamiento por recuento , pueden tener un mejor rendimiento. Los algoritmos asintóticamente óptimos se conocen desde mediados del siglo XX; todavía se están inventando nuevos algoritmos útiles; el Timsort, ahora ampliamente utilizado, data de 2002, y el tipo de biblioteca se publicó por primera vez en 2006.
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.
Clasificación
Los algoritmos de clasificación a menudo se clasifican por:
- Complejidad computacional ( peor, promedio y mejor comportamiento) en términos del tamaño de la lista ( n ). Para los algoritmos de clasificación en serie típicos, el buen comportamiento es O ( n log n ), con ordenamiento paralelo en O (log 2 n ), y el mal comportamiento es O ( n 2 ). (Consulte la notación Big O ). El comportamiento ideal para una ordenación en serie es O ( n ), pero esto no es posible en el caso promedio. La clasificación paralela óptima es O (log n ). Los algoritmos de clasificación basados en comparación necesitan al menos comparaciones de Ω ( n log n ) para la mayoría de las entradas.
- Complejidad computacional de los intercambios (para algoritmos "in situ").
- Uso de memoria (y uso de otros recursos informáticos). En particular, algunos algoritmos de clasificación están " en el lugar ". Estrictamente, una clasificación en el lugar solo necesita memoria O (1) más allá de los elementos que se clasifican; a veces, la memoria adicional O (log ( n )) se considera "in situ".
- Recurrencia. Algunos algoritmos son recursivos o no recursivos, mientras que otros pueden ser ambos (p. Ej., Clasificación por fusión).
- Estabilidad: los algoritmos de clasificación estables mantienen el orden relativo de los registros con claves iguales (es decir, valores).
- Si son o no un tipo de comparación . Una clasificación de comparación examina los datos solo comparando dos elementos con un operador de comparación.
- Método general: inserción, intercambio, selección, fusión, etc. Los tipos de intercambio incluyen clasificación de burbujas y clasificación rápida. Los tipos de selección incluyen clasificación por agitador y clasificación en pila.
- Si el algoritmo es en serie o en paralelo. El resto de esta discusión se concentra casi exclusivamente en algoritmos seriales y asume el funcionamiento en serie.
- Adaptabilidad: si la clasificación previa de la entrada afecta el tiempo de ejecución. Se sabe que los algoritmos que tienen esto en cuenta son adaptativos .
Estabilidad
Los algoritmos de clasificación estables clasifican los elementos repetidos en el mismo orden en que aparecen en la entrada. Al ordenar algunos tipos de datos, solo se examina una parte de los datos al determinar el orden de clasificación. Por ejemplo, en el ejemplo de clasificación de cartas de la derecha, las cartas se ordenan por rango y su palo se ignora. Esto permite la posibilidad de múltiples versiones diferentes ordenadas correctamente de la lista original. Los algoritmos de clasificación estables eligen uno de estos, de acuerdo con la siguiente regla: si dos elementos se comparan como iguales, como las dos tarjetas de 5, entonces se conservará su orden relativo, de modo que si uno vino antes que el otro en la entrada, también lo hará. vienen antes que el otro en la salida.
La estabilidad es importante por la siguiente razón: digamos que los registros de los estudiantes que constan de nombre y sección de clase se ordenan dinámicamente en una página web, primero por nombre, luego por sección de clase en una segunda operación. 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 ordenación inestable, podría ser que la ordenación por sección mezcle el orden de los nombres. Usando una clasificación estable, los usuarios pueden elegir ordenar por sección y luego por nombre, primero ordenando usando el nombre y luego volviendo a ordenar usando la sección, lo que resulta en la preservación del orden de los nombres. (Algunos programas de hojas de cálculo obedecen este comportamiento: ordenar por nombre, luego por sección produce una lista alfabética de estudiantes por sección).
Otra razón: la ordenación inestable puede producir una salida diferente para la misma entrada de una ejecución a otra. Tal comportamiento no es adecuado para algunas aplicaciones, por ejemplo, para aplicaciones cliente-servidor donde el servidor usa la paginación para la salida y realiza una nueva búsqueda y clasificación para cada nueva página solicitada por el cliente.
Más formalmente, los datos que se ordenan se pueden representar como un registro o tupla de valores, y la parte de los datos que se usa para ordenar se llama clave . En el ejemplo de la tarjeta, las tarjetas 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 los elementos iguales son indistinguibles, como los números enteros, o más en general, 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 hacer esto es extender artificialmente la comparación de claves, de modo que las comparaciones entre dos objetos con claves iguales se decidan usando el orden de las entradas en la lista de entrada original como un desempate. Sin embargo, recordar este orden puede requerir tiempo y espacio adicionales.
Una aplicación para los algoritmos de clasificación estables es clasificar una lista usando 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 ( ♥ ), espadas (♠), y dentro de cada palo, las cartas están ordenadas por rango. Esto se puede hacer primero clasificando las cartas por rango (usando cualquier tipo), y luego haciendo una clasificación estable por palo:
Dentro de cada palo, el tipo estable conserva el orden por rango que ya estaba hecho. Esta idea se puede extender a cualquier número de claves y se utiliza mediante ordenación por radix . El mismo efecto se puede lograr con una clasificación inestable mediante el uso de una comparación de clave lexicográfica, que, por ejemplo, compara primero por palo y luego compara por rango si los palos son iguales.
Comparación de algoritmos
En esta tabla, n es el número de registros que se ordenarán. Las columnas "Promedio" y "Peor" dan la complejidad de tiempo en cada caso, bajo el supuesto de que la longitud de cada clave es constante y que, por lo tanto, todas las comparaciones, intercambios y otras operaciones necesarias pueden realizarse en tiempo constante. "Memoria" denota la cantidad de almacenamiento auxiliar necesario más allá de la utilizada por la propia lista, bajo el mismo supuesto. Los tiempos de ejecución y los requisitos de memoria que se enumeran a continuación deben entenderse 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 .
Clases de comparación
A continuación se muestra una tabla de tipos de comparación . Una clasificación de comparación no puede funcionar mejor que O ( n log n ) en promedio. [4]
Nombre | Mejor | Promedio | Peor | Memoria | Estable | Método | Otras notas |
---|---|---|---|---|---|---|---|
Ordenación rápida | No | Fraccionamiento | La ordenación rápida generalmente se realiza en el lugar con espacio de pila O (log n ) . [5] [6] | ||||
Combinar ordenación | norte | sí | Fusión | Altamente paralelizable (hasta O (log n ) utilizando el algoritmo de los tres húngaros). [7] | |||
Ordenación por combinación in situ | - | - | 1 | sí | Fusión | Se puede implementar como una ordenación estable basada en una fusión in situ estable. [8] | |
Introsort | No | Partición y selección | Utilizado en varias implementaciones de STL . | ||||
Heapsort | 1 | No | Selección | ||||
Tipo de inserción | norte | 1 | sí | Inserción | O ( n + d ) , en el peor de los casos sobre secuencias que tienen d inversiones . | ||
Orden de bloque | norte | 1 | sí | Inserción y fusión | Combinar un bloque basado algoritmo de fusión in situ [9] con una ordenación de fusión ascendente . | ||
Quadsort | norte | norte | sí | Fusión | Utiliza una red de clasificación de 4 entradas . [10] | ||
Timsort | norte | norte | sí | Inserción y fusión | Hace n comparaciones cuando los datos ya están ordenados o ordenados al revés. | ||
Orden de selección | 1 | No | Selección | Estable con espacio adicional o cuando se utilizan listas vinculadas. [11] | |||
Cubesort | norte | norte | sí | Inserción | Hace n comparaciones cuando los datos ya están ordenados o ordenados al revés. | ||
Shellsort | 1 | No | Inserción | Tamaño de código pequeño. | |||
Ordenamiento de burbuja | norte | 1 | sí | Intercambiar | Diminuto tamaño de código. | ||
Tipo de árbol | norte | sí | Inserción | Cuando se utiliza un árbol de búsqueda binario autoequilibrado . | |||
Orden de ciclo | 1 | No | Selección | En el lugar con un número teóricamente óptimo de escrituras. | |||
Orden de biblioteca | norte | No | Inserción | Similar a una ordenación de inserción con huecos. Requiere permutar aleatoriamente la entrada para garantizar límites de tiempo de alta probabilidad, lo que la hace no estable. | |||
Clasificación de paciencia | norte | norte | No | Inserción y selección | Encuentra todas las subsecuencias crecientes más largas en O ( n log n ) . | ||
Smoothsort | norte | 1 | No | Selección | Una variante adaptativa de heapsort basada en la secuencia de Leonardo en lugar de un montón binario tradicional . | ||
Tipo de hebra | norte | norte | sí | Selección | |||
Tipo de torneo | n [12] | No | Selección | Variación del tipo de pila. | |||
Tipo de coctelera | norte | 1 | sí | Intercambiar | Una variante de Bubblesort que trata bien con valores pequeños al final de la lista | ||
Tipo de peine | 1 | No | Intercambiar | Más rápido que la clasificación de burbujas en promedio. | |||
Tipo de gnomo | norte | 1 | sí | Intercambiar | Diminuto tamaño de código. | ||
Desorganizar ordenación [13] | norte | kn | kn | norte | No | Distribución y fusión | No se realizan intercambios. El parámetro k es proporcional a la entropía en la entrada. k = 1 para entrada ordenada o en orden inverso. |
El método de Franceschini [14] | norte | 1 | sí | ? | Realiza O ( n ) movimientos de datos. | ||
Tipo impar-par | norte | 1 | sí | Intercambiar | Se puede ejecutar fácilmente en procesadores paralelos. |
Clases sin comparación
La siguiente tabla describe los algoritmos de clasificación de enteros y otros algoritmos de clasificación que no son tipos de comparación . Como tales, no se limitan a Ω ( n log n ) . [15] Complejidades siguientes se supone n artículos a clasificar, con teclas de tamaño k , tamaño dígitos d , y r el rango de números a ser clasificada. Muchos de ellos se basan en la suposición 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 menos que". En el modelo de máquina de acceso aleatorio de costo unitario , los algoritmos con tiempo de ejecución de, como la ordenación por radix, todavía toma un tiempo proporcional a Θ ( n log n ) , porque n está limitado a no ser más de, y una mayor cantidad de elementos para ordenar requeriría una k mayor para almacenarlos en la memoria. [dieciséis]
Nombre | Mejor | Promedio | Peor | Memoria | Estable | n ≪ 2 k | Notas |
---|---|---|---|---|---|---|---|
Tipo de casillero | - | sí | sí | No se pueden ordenar los números no enteros. | |||
Clasificación de cubos (llaves uniformes) | - | sí | No | Asume una distribución uniforme de elementos del dominio en la matriz. [17] Tampoco puede ordenar números no enteros | |||
Orden de depósito (claves de números enteros) | - | sí | sí | Si r es, entonces la complejidad del tiempo promedio es . [18] | |||
Contando ordenar | - | sí | sí | Si r es, entonces la complejidad del tiempo promedio es . [17] | |||
Clasificación de LSD Radix | sí | No | niveles de recursividad, 2 d para la matriz de conteo. [17] [18] A diferencia de la mayoría de los tipos de distribución, esto puede ordenar números de coma flotante , números negativos y más. | ||||
Tipo de Radix MSD | - | sí | No | La versión estable usa una matriz externa de tamaño n para contener todos los contenedores. Al igual que la variante LSD, puede ordenar números no enteros. | |||
MSD Radix Sort (en el lugar) | - | No | No | d = 1 para in situ, niveles de recursividad, sin matriz de recuento. | |||
Spreadsort | norte | No | No | Los asintóticos se basan en el supuesto de que n ≪ 2 k , pero el algoritmo no lo requiere. | |||
Burstsort | - | No | No | Tiene mejor factor constante que la ordenación por radix para ordenar cadenas. Aunque depende un poco de las características específicas de las cadenas que se encuentran comúnmente. | |||
Flashsort | norte | norte | No | No | Requiere una distribución uniforme de elementos del dominio en la matriz para ejecutarse en tiempo lineal. Si la distribución está muy sesgada, entonces puede volverse cuadrática si la ordenación subyacente es cuadrática (generalmente es una ordenación por inserción). La versión local no es estable. | ||
Tipo de cartero | - | - | No | Una variación del tipo de cubeta, que funciona de manera muy similar a MSD Radix Sort. Específico para las necesidades del servicio postal. |
Samplesort se puede usar para paralelizar cualquiera de los tipos de no comparación, distribuyendo de manera eficiente los datos en varios depósitos y luego pasando la clasificación a varios procesadores, sin necesidad de fusionarlos, ya que los depósitos ya están ordenados entre sí.
Otros
Algunos algoritmos son lentos en comparación con los discutidos anteriormente, como el bogosort con tiempo de ejecución ilimitado y el tipo de títere que tiene un tiempo de ejecución O ( n 2.7 ). Estos tipos se describen generalmente 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 bajo o requisitos de hardware especializados.
Nombre | Mejor | Promedio | Peor | Memoria | Estable | Comparación | Otras notas |
---|---|---|---|---|---|---|---|
Tipo de cuentas | norte | S | S | N / A | No | Funciona solo con números enteros positivos. Requiere hardware especializado para su funcionamiento garantizado.hora. Existe la posibilidad de implementación de software, pero el tiempo de ejecución será, donde S es la suma de todos los números enteros que se van a ordenar, en el caso de los números enteros pequeños se puede considerar lineal. | |
Tipo de panqueques simple | - | norte | norte | No | sí | El recuento es el número de vueltas. | |
Tipo de espagueti (encuesta) | norte | norte | norte | sí | Votación | Este es un algoritmo analógico de tiempo lineal para ordenar una secuencia de elementos, que requiere un espacio de pila O ( n ), y la ordenación es estable. Esto requiere n procesadores en paralelo. Ver análisis de # de clasificación de espaguetis . | |
Red de clasificación | Varía (las redes de clasificación estables requieren más comparaciones) | sí | El orden de las comparaciones se establece de antemano en función de un tamaño de red fijo. Impracticable para más de 32 artículos. [ disputado ] | ||||
Clasificador bitónico | No | sí | Una variación eficaz de las redes de clasificación. | ||||
Bogosort | norte | ilimitado (cierto), (esperado) | 1 | No | sí | Mezcla aleatoria. Se usa solo con fines de ejemplo, ya que incluso el tiempo de ejecución esperado en el mejor de los casos es terrible. [19] | |
Tipo chiflado | norte | No | sí | Más lento que la mayoría de los algoritmos de clasificación (incluso los ingenuos) con una complejidad de tiempo de O ( n log 3 / log 1.5 ) = O ( n 2.7095 ... ) . |
Los científicos 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:
- El algoritmo de Thorup , un algoritmo aleatorio para ordenar claves de un dominio de tamaño finito, tomando O ( n log log n ) tiempo y O ( n ) espacio. [20]
- Un algoritmo de ordenación de enteros aleatorios que tomatiempo esperado y espacio O ( n ). [21]
Algoritmos de clasificación populares
Si bien hay una gran cantidad de algoritmos de clasificación, en las implementaciones prácticas predominan algunos 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 por pila, ordenación por combinación o ordenación rápida. Las implementaciones eficientes generalmente usan un algoritmo híbrido , que combina un algoritmo asintóticamente eficiente para el ordenamiento general con el ordenamiento por inserción para listas pequeñas en la parte inferior de una recursividad. Las implementaciones altamente ajustadas usan variantes más sofisticadas, como Timsort (ordenación por fusión, ordenación por inserción y lógica adicional), que se usa en Android, Java y Python, e introsort ( ordenación rápida y ordenación por montón), que se usa (en formas variantes) en algunos C ++ ordenar implementaciones y en .NET.
Para datos más restringidos, como números en un intervalo fijo, se utilizan ampliamente los tipos de distribución , como el ordenamiento por conteo o el ordenamiento por base. La clasificación y las variantes de las burbujas rara vez se utilizan en la práctica, pero se encuentran comúnmente en la enseñanza y las discusiones teóricas.
Cuando se clasifican objetos físicamente (como alfabetizar trabajos, exámenes o libros), la gente generalmente usa intuitivamente ordenamientos de inserción para conjuntos pequeños. En el caso de conjuntos más grandes, la gente suele primero el balde, por ejemplo, por la letra inicial, y el agrupamiento múltiple permite clasificar de forma práctica conjuntos muy grandes. A menudo, el espacio es relativamente barato, por ejemplo, al esparcir objetos en el piso o en un área grande, pero las operaciones son costosas, particularmente mover un objeto a una gran distancia; la localidad de referencia es importante. Las clasificaciones de combinación también son prácticas para objetos físicos, en particular porque se pueden usar dos manos, una para que cada lista se combine, mientras que otros algoritmos, como la clasificación de pila o la clasificación rápida, no son adecuados para el uso humano. Otros algoritmos, como el ordenamiento por biblioteca , una variante del ordenamiento por inserción que deja espacios, también son prácticos para uso físico.
Clases simples
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 la baja sobrecarga, pero no eficientes en datos grandes. El ordenamiento por inserción es generalmente más rápido que el ordenamiento por selección en la práctica, debido a menos comparaciones y buen rendimiento en datos casi ordenados, y por lo tanto se prefiere en la práctica, pero el ordenamiento por selección usa menos escrituras y, por lo tanto, se usa cuando el rendimiento de escritura es un factor limitante.
Tipo de inserción
La ordenación por inserción es un algoritmo de ordenación simple que es relativamente eficiente para listas pequeñas y en su mayoría listas 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 ponemos dinero en nuestra billetera. [22] En los arreglos, la nueva lista y los elementos restantes pueden compartir el espacio del arreglo, pero la inserción es costosa y requiere cambiar todos los elementos siguientes uno por uno. Shellsort (ver más abajo) es una variante del ordenamiento por inserción que es más eficiente para listas más grandes.
Orden de selección
La clasificación por selección es una clasificación por comparación in situ . Tiene una complejidad O ( n 2 ), lo que lo hace ineficaz en listas grandes y, en general, funciona peor que el tipo de inserción similar . El ordenamiento por selección se 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 en la primera posición y repite estos pasos para el resto de la lista. [23] No hace más de n intercambios y, por lo tanto, es útil cuando el intercambio es muy caro.
Clases eficientes
Los algoritmos prácticos de clasificación general casi siempre se basan en un algoritmo con una complejidad de tiempo promedio (y generalmente una complejidad en el peor de los casos) O ( n log n ), de los cuales los más comunes son la clasificación por pila, la clasificación por combinación y la clasificación rápida. Cada uno tiene ventajas e inconvenientes, siendo el más significativo que la implementación simple de la ordenación por fusión usa un espacio adicional O ( n ), y la implementación simple de la ordenación rápida tiene una complejidad en el peor de los casos O ( n 2 ). Estos problemas pueden resolverse o mejorarse a costa de un algoritmo más complejo.
Si bien estos algoritmos son asintóticamente eficientes en datos aleatorios, para una eficacia práctica en datos del mundo real se utilizan varias modificaciones. Primero, la sobrecarga de estos algoritmos se vuelve significativa en datos más pequeños, por lo que a menudo se usa un algoritmo híbrido, que comúnmente cambia a la 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 se pueden clasificar en O ( n ) tiempo mediante algoritmos apropiados. Por último, también pueden ser inestables , y la estabilidad es a menudo una propiedad deseable en cierto tipo. Por lo tanto, a menudo se emplean algoritmos más sofisticados, como Timsort (basado en el ordenamiento por fusión) o introsort (basado en el ordenamiento rápido, recurriendo al ordenamiento de pila).
Combinar ordenació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 viene 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 escala bien a listas muy grandes, porque su peor tiempo de ejecución es O ( n log n ). También se aplica fácilmente a listas, no solo matrices, ya que solo requiere acceso secuencial, no acceso aleatorio. Sin embargo, tiene una complejidad adicional en el espacio O ( n ) e involucra un gran número de copias en implementaciones simples.
Merge sort ha visto un aumento relativamente reciente en popularidad para implementaciones prácticas, debido a su uso en el algoritmo sofisticado 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] ). . Merge sort 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
Heapsort es una versión mucho más eficiente del ordenamiento 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 continuando con el resto de la lista, pero realiza 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 para que el elemento más grande restante se mueva a la raíz. Usando el montón, encontrar el siguiente elemento más grande toma O (log n ) tiempo, en lugar de O ( n ) para un escaneo lineal como en la ordenación de selección simple. Esto permite que Heapsort se ejecute en tiempo O ( n log n ), y esta también es la complejidad del peor de los casos.
Ordenación rápida
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 e in situ . Las sublistas mayores y menores 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 particiones 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 peor desempeño es O ( n 2 ); aunque esto es raro, en implementaciones ingenuas (eligiendo el primer o último elemento como pivote) esto ocurre para datos ordenados, que es un caso común. El problema más complejo en el ordenamiento rápido es, por lo tanto, elegir un buen elemento de pivote, ya que las elecciones consistentemente malas de pivotes pueden resultar en un rendimiento de O ( n 2 ) drásticamente más lento , pero una buena elección de pivotes produce un rendimiento de 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, como por medio del algoritmo de selección de la mediana de las medianas , es una operación O ( n ) en listas no clasificadas y, por lo tanto, exige una sobrecarga significativa con la clasificación. En la práctica, la elección de un pivote aleatorio casi con certeza produce un rendimiento O ( n log n ).
Shellsort
Shellsort fue inventado por Donald Shell en 1959. [32] Mejora el ordenamiento por inserción al mover 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 entiempo, 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 en su mayoría están ordenados, con solo unos pocos elementos fuera de lugar, funcionan más rápido. Por lo tanto, al ordenar primero los elementos que están lejos y reducir progresivamente la brecha entre los elementos para ordenar, la ordenació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 la ordenación por inserción.
La complejidad de tiempo en el peor de los casos de Shellsort es un problema abierto y depende de la secuencia de huecos utilizada, con complejidades conocidas que van desde O ( n 2 ) a O ( n 4/3 ) y Θ ( n log 2 n ). Esto, combinado con el hecho de que Shellsort está en su lugar , solo necesita una cantidad relativamente pequeña de código y no requiere el uso de la pila de llamadas , hace que sea útil en situaciones en las que la memoria es escasa, como en los sistemas integrados. y núcleos del sistema operativo .
Clases y variantes de burbujas
La clasificación de burbujas y variantes como la clasificación de concha y la clasificación de cóctel son algoritmos de clasificación simples y altamente ineficientes. Se ven con frecuencia en los textos introductorios debido a la facilidad de análisis, pero rara vez se utilizan en la práctica.
Ordenamiento de burbuja
La clasificación de burbujas es un algoritmo de clasificación simple. El algoritmo comienza al comienzo 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 y se repite hasta que no se hayan producido cambios en la última pasada. [33] El tiempo promedio de este algoritmo y el desempeño en el peor de los casos es O ( n 2 ), por lo que rara vez se usa para clasificar conjuntos de datos grandes y desordenados. La clasificación de burbujas se puede utilizar para clasificar una pequeña cantidad de elementos (donde su ineficiencia asintótica no es una penalización alta). La clasificación de burbujas también se puede usar de manera eficiente en una lista de cualquier longitud que esté casi ordenada (es decir, los elementos no están significativamente fuera de lugar). Por ejemplo, si cualquier número de elementos está 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 el primer paso, el segundo paso encontrará todos los elementos en orden, por lo que el orden será toma solo 2 n tiempo.
[34]
Tipo de peine
La clasificación por 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. [35] Más tarde fue redescubierto y popularizado por Stephen Lacey y Richard Box con un artículo de Byte Magazine 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) Esto se logra intercambiando inicialmente elementos que están a cierta distancia entre sí en la matriz, en lugar de solo intercambiar elementos si están 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 una cierta distancia entre sí, la ordenación en peine puede considerarse como la misma generalización aplicada a la ordenación por burbujas.
Tipo de distribución
La clasificación de distribución se refiere a cualquier algoritmo de clasificación donde los datos se distribuyen desde su entrada a múltiples estructuras intermedias que luego se recopilan y colocan en la salida. Por ejemplo, tanto cubo especie y flashsort son de distribución basados en algoritmos de ordenació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.
Contando ordenar
El ordenamiento por conteo es aplicable cuando se sabe que cada entrada pertenece a un conjunto particular, S , de posibilidades. El algoritmo se ejecuta en la memoria O (| S | + n ) tiempo y O (| S |) donde n es la longitud de la entrada. Funciona creando una matriz entera de tamaño | S | y usar el i- ésimo bin para contar las apariciones del i- ésimo miembro de S en la entrada. Luego, cada entrada se cuenta incrementando el valor de su ubicación correspondiente. Luego, la matriz de conteo se recorre en bucle 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.
Tipo de cubo
La ordenación de cubos es un algoritmo de clasificación de divide y vencerás que generaliza la ordenación de conteo dividiendo una matriz en un número finito de cubos. Luego, cada depósito se clasifica individualmente, ya sea mediante un algoritmo de clasificación diferente o aplicando de forma recursiva el algoritmo de clasificación de depósitos.
Una clasificación de depósito funciona mejor cuando los elementos del conjunto de datos se distribuyen uniformemente en todos los depósitos.
Orden de radix
La ordenación por radix es un algoritmo que ordena números procesando dígitos individuales. n números que constan de k dígitos cada uno se ordenan en O ( n · k ) tiempo. La clasificación por radix puede procesar dígitos de cada número, ya sea comenzando desde el dígito menos significativo (LSD) o comenzando desde el dígito más significativo (MSD). El algoritmo LSD primero ordena la lista por el dígito menos significativo mientras preserva su orden relativo usando un ordenamiento estable. Luego los ordena 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 de base LSD requiere el uso de una clasificación estable, el algoritmo de clasificación de base MSD no lo requiere (a menos que se desee una clasificación estable). La ordenación por radix de MSD in situ no es estable. Es común que el algoritmo de ordenación de conteo sea utilizado internamente por la ordenación de radix. Un enfoque de clasificación híbrido , como el uso de la clasificación por inserción para contenedores pequeños, mejora significativamente el rendimiento de la clasificación por radix.
Patrones de uso de memoria y clasificación de índices
Cuando el tamaño de la matriz que se va a clasificar 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 encaja fácilmente en la RAM puede volverse 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 ), 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 la 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 lento hacia y desde el disco. En ese escenario, puede ser preferible otro algoritmo incluso si requiere comparaciones más totales.
Una forma de solucionar este problema, que funciona bien cuando los registros complejos (como en una base de datos relacional ) se ordenan por un campo clave relativamente pequeño, es crear un índice en la matriz y luego ordenar el índice, en lugar de todo el formación. (Se puede producir una versión ordenada de toda la matriz con una pasada, leyendo del í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 lo haría todo el arreglo, eliminando efectivamente el problema de intercambio de disco. Este procedimiento a veces se denomina "clasificación de etiquetas". [36]
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 manera que se 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, el contenido de cada fragmento ordenado usando un algoritmo eficiente (como quicksort ) y los resultados fusionados usando una combinación de k -way similar a la utilizada en mergesort . Esto es más rápido que realizar una ordenación por combinación o una ordenación rápida en toda la lista. [37] [38]
Las técnicas también se pueden combinar. Para ordenar conjuntos de datos muy grandes que exceden ampliamente la memoria del sistema, incluso el índice puede necesitar ser ordenado usando un algoritmo o una combinación de algoritmos diseñados para funcionar razonablemente con memoria virtual , es decir, para reducir la cantidad de intercambio requerido.
Algoritmos relacionados
Los problemas relacionados incluyen la ordenación parcial (ordenando solo los k elementos más pequeños de una lista o, alternativamente, calculando los k elementos más pequeños, pero desordenados) y la selección (calculando 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, que a menudo se derivan 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 . A la inversa, algunos algoritmos de clasificación se pueden derivar mediante la aplicación repetida de un algoritmo de selección; Quicksort y quickselect pueden verse como el mismo movimiento pivotante, difiriendo solo en si uno recurre en ambos lados (quicksort, divide y vencerás ) o en un lado (quickselect, disminuir y conquistar ).
Una especie de opuesto de 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: asignando un número aleatorio a cada elemento de la lista y luego clasificando 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: la baraja de Fisher-Yates .
Ver también
- Recopilación : ensamblaje de información escrita en un pedido estándar
- Transformada de Schwartzian
- Algoritmo de búsqueda : cualquier algoritmo que resuelva el problema de búsqueda.
- Clasificación cuántica : algoritmos de clasificación para computadoras cuánticas
Referencias
- ^ "Conoce a las 'señoras del refrigerador' que programaron el ENIAC" . Hilo mental . 2013-10-13 . Consultado el 16 de junio de 2016 .
- ^ Lohr, Steve (17 de diciembre de 2001). "Frances E. Holberton, 84, programador informático temprano" . NYTimes . Consultado el 16 de diciembre de 2014 .
- ^ Demuth, Howard B. (1956). Clasificación electrónica de datos (tesis doctoral). Universidad Stanford. ProQuest 301940891 .
- ^ Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L .; Stein, Clifford (2009), "8", Introducción a los algoritmos (3ª ed.), Cambridge, MA: The MIT Press, p. 167, ISBN 978-0-262-03293-3
- ^ Sedgewick, Robert (1 de septiembre de 1998). Algoritmos en C: fundamentos, estructuras de datos, clasificación, búsqueda, partes 1-4 (3 ed.). Educación Pearson. ISBN 978-81-317-1291-7. Consultado el 27 de noviembre de 2012 .
- ^ Sedgewick, R. (1978). "Implementación de programas Quicksort". Comm. ACM . 21 (10): 847–857. doi : 10.1145 / 359619.359631 .
- ^ Ajtai, M .; Komlós, J .; Szemerédi, E. (1983). Una red de clasificación O (n log n) . STOC '83. Actas del decimoquinto simposio anual ACM sobre teoría de la computación . págs. 1–9. doi : 10.1145 / 800061.808726 . ISBN 0-89791-099-0.
- ^ Huang, BC; Langston, MA (diciembre de 1992). "Fusión y clasificación estable y rápida en un espacio adicional constante". Computación. J. 35 (6): 643–650. CiteSeerX 10.1.1.54.8381 . doi : 10.1093 / comjnl / 35.6.643 .
- ^ Kim, PS; Kutzner, A. (2008). Fusión estable en el lugar basada en proporciones . TAMC 2008. Teoría y Aplicaciones de Modelos de Computación . LNCS . 4978 . págs. 246-257. CiteSeerX 10.1.1.330.2641 . doi : 10.1007 / 978-3-540-79228-4_22 . ISBN 978-3-540-79227-7.
- ^ https://qiita.com/hon_no_mushi/items/92ff1a220f179b8d40f9
- ^ "CLASIFICACIÓN DE SELECCIÓN (Java, C ++) - Algoritmos y estructuras de datos" . www.algolist.net . Consultado el 14 de abril de 2018 .
- ^ http://dbs.uni-leipzig.de/skripte/ADS1/PDF4/kap4.pdf
- ^ Kagel, Art (noviembre de 1985). "Desorganizar, no del todo". Lenguaje informático . 2 (11).
- ^ Franceschini, G. (junio de 2007). "Clasificación estable, en el lugar, con comparaciones O (n log n) y movimientos O (n)". Teoría de los sistemas informáticos . 40 (4): 327–353. doi : 10.1007 / s00224-006-1311-1 .
- ^ Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L .; Stein, Clifford (2001), "8", Introducción a los algoritmos (2ª ed.), Cambridge, MA: The MIT Press, p. 165, ISBN 0-262-03293-7
- ^ Nilsson, Stefan (2000). "¿El algoritmo de clasificación más rápido?" . Dr. Dobb's .
- ^ a b c Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L .; Stein, Clifford (2001) [1990]. Introducción a los algoritmos (2ª ed.). MIT Press y McGraw-Hill. ISBN 0-262-03293-7.
- ^ a b Goodrich, Michael T .; Tamassia, Roberto (2002). "4.5 Clasificación por cubos y clasificación por radios". Diseño de algoritmos: fundamentos, análisis y ejemplos de Internet . John Wiley e hijos. págs. 241–243. ISBN 978-0-471-38365-9.
- ^ Gruber, H .; Holzer, M .; Ruepp, O., "Sorting the slow way: an analysis of perversamente horribles algoritmos de ordenación aleatorios", 4ta Conferencia Internacional sobre Diversión con Algoritmos, Castiglioncello, Italia, 2007 (PDF) , Lecture Notes in Computer Science, 4475 , Springer-Verlag, págs. 183–197, doi : 10.1007 / 978-3-540-72914-3_17.
- ^ Thorup, M. (febrero de 2002). "Clasificación aleatoria en O (n log log n) Tiempo y espacio lineal mediante operaciones booleanas de suma, desplazamiento y bits". Revista de algoritmos . 42 (2): 205–230. doi : 10.1006 / jagm.2002.1211 .
- ^ Han, Yijie; Thorup, M. (2002). Clasificación de enteros en O (n√ (log log n)) tiempo esperado y espacio lineal . El 43º Simposio Anual del IEEE sobre Fundamentos de las Ciencias de la Computación . págs. 135-144. doi : 10.1109 / SFCS.2002.1181890 . ISBN 0-7695-1822-2.
- ^ Wirth, Niklaus (1986), Algoritmos y estructuras de datos , Upper Saddle River, Nueva Jersey: Prentice-Hall, págs. 76–77, ISBN 978-0130220059
- ^ Wirth 1986 , págs. 79–80
- ^ Wirth 1986 , págs. 101-102
- ^ "Descripción original de Tim Peters de timsort" . python.org . Consultado el 14 de abril de 2018 .
- ^ "TimSort.java de OpenJDK" . java.net . Consultado el 14 de abril de 2018 .
- ^ "sort - perldoc.perl.org" . perldoc.perl.org . Consultado el 14 de abril de 2018 .
- ^ Combinar ordenación en Java 1.3 , Sun. Archivado el 4 de marzo de 2009 en la Wayback Machine.
- ^ Wirth 1986 , págs. 87–89
- ^ Wirth 1986 , p. 93
- ^ Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L .; Stein, Clifford (2009), Introducción a los algoritmos (3ª ed.), Cambridge, MA: The MIT Press, págs. 171-172, ISBN 978-0262033848
- ^ Shell, DL (1959). "Un procedimiento de clasificación de alta velocidad" (PDF) . Comunicaciones de la ACM . 2 (7): 30–32. doi : 10.1145 / 368370.368387 .
- ^ Wirth 1986 , págs. 81–82
- ^ "núcleo / grupos.c" . Consultado el 5 de mayo de 2012 .
- ^ Brejová, B. (15 de septiembre de 2001). "Análisis de variantes de Shellsort". Inf. Proceso. Letón. 79 (5): 223-227. doi : 10.1016 / S0020-0190 (00) 00223-4 .
- ^ "Definición de clasificación de etiquetas de PC Magazine Encyclopedia" . www.pcmag.com . Consultado el 14 de abril de 2018 .
- ^ Donald Knuth , El arte de la programación informática , volumen 3: clasificación y búsqueda , segunda edición. Addison-Wesley, 1998, ISBN 0-201-89685-0 , Sección 5.4: Clasificación externa, págs. 248–379.
- ^ Ellis Horowitz y Sartaj Sahni , Fundamentos de estructuras de datos , H. Freeman & Co., ISBN 0-7167-8042-9 .
Otras lecturas
- Knuth, Donald E. (1998), Clasificación y búsqueda , El arte de la programación informática, 3 (2a ed.), Boston: Addison-Wesley, ISBN 0-201-89685-0
- Sedgewick, Robert (1980), "Clasificación eficiente por computadora: Introducción", Probatational Probability , Nueva York: Academic Press, págs. 101-130 , ISBN 0-12-394680-8
enlaces externos
- Clasificación de animaciones de algoritmos en Wayback Machine (archivado el 3 de marzo de 2015)
- Algoritmos de clasificación secuenciales y paralelos : explicaciones y análisis de muchos algoritmos de clasificación
- Diccionario de algoritmos, estructuras de datos y problemas : diccionario de algoritmos, técnicas, funciones comunes y problemas.
- Vista ligeramente escéptica sobre los algoritmos de clasificación : analiza varios algoritmos clásicos y promueve alternativas al algoritmo de clasificación rápida.
- 15 algoritmos de clasificación en 6 minutos (Youtube) : visualización y "audibilización" de 15 algoritmos de clasificación en 6 minutos
- Secuencia A036604 en la base de datos OEIS titulada "Clasificación de números: número mínimo de comparaciones necesarias para clasificar n elementos" , que se realizó mediante el algoritmo de Ford – Johnson
- Algoritmos de clasificación utilizados en pinturas famosas (Youtube) : visualización de algoritmos de clasificación en muchas pinturas famosas.