Algoritmo de clasificación

Un algoritmo que organiza listas en orden.

En informática , un algoritmo de clasificación es un algoritmo que pone los 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.

Formalmente, la salida de cualquier algoritmo de clasificación debe satisfacer dos condiciones:

1. La salida está en orden monótono (cada elemento no es más pequeño / más grande que el elemento anterior, de acuerdo con el orden requerido)
2. 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 deben almacenarse en una estructura de datos que permita el acceso aleatorio en lugar de una que solo permita el acceso secuencial .

Historia y conceptos

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 , quien trabajó en ENIAC y UNIVAC . ^{[1] [2]} El tipo de burbuja 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 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 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 matrices pequeñas 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 matrices muy pequeñas (<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 se pueden clasificar por:

• Complejidad computacional
  • Comportamiento de caso mejor, peor y promedio en términos del tamaño de la lista. Para los algoritmos de clasificación en serie típicos, el buen comportamiento es O ( n  log  n ), con el ordenamiento paralelo en O (log ²  n ) y el mal comportamiento es O ( n ² ). 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 ).
  • Cambios por 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".
• Recursión: algunos algoritmos son recursivos o no recursivos, mientras que otros pueden ser ambos (p. Ej., Combinación de ordenació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 ordenamientos de selección incluyen ordenamiento cíclico y ordenamiento dinámico.
• 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 .
• En línea: un algoritmo como el ordenamiento por inserción que está en línea puede ordenar un flujo constante de entrada.

Estabilidad

Un ejemplo de tipo estable en naipes. Cuando las cartas se ordenan por rango con una clasificación estable, los dos 5 deben permanecer en el mismo orden en la salida clasificada en la que estaban originalmente. Cuando se clasifican con una clasificación no estable, los 5 pueden terminar en el lado opuesto. orden en la salida ordenada.

Los algoritmos de clasificación estables clasifican los elementos repetidos 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 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 ordenación estable eligen uno de estos, de acuerdo con la siguiente regla: si dos elementos se comparan como iguales (como las dos 5 cartas), entonces se conservará su orden relativo, es decir, si uno viene antes que el otro en la entrada, vendrá antes que el otro en la salida.

La estabilidad es importante para preservar el orden en varios tipos en el mismo conjunto de datos . Por ejemplo, digamos 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.

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 manera 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 "Mejor", "Promedio" y "Peor" dan la complejidad del tiempo en cada caso, bajo el supuesto de que la longitud de cada clave es constante y, por lo tanto, 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 ² n significa (log n ) ² .

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]

Clases de comparación

Nombre	Mejor	Promedio	Peor	Memoria	Estable	Método	Otras notas
Ordenación rápida	${\displaystyle n\log n}$	${\displaystyle n\log n}$	${\displaystyle n^{2}}$	${\displaystyle \log n}$	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	${\displaystyle n\log n}$	${\displaystyle n\log n}$	${\displaystyle n\log 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	-	-	${\displaystyle n\log ^{2}n}$	1	sí	Fusión	Se puede implementar como una ordenación estable basada en una fusión in situ estable. [8]
Introsort	${\displaystyle n\log n}$	${\displaystyle n\log n}$	${\displaystyle n\log n}$	${\displaystyle \log n}$	No	Partición y selección	Utilizado en varias implementaciones de STL .
Heapsort	${\displaystyle n\log n}$	${\displaystyle n\log n}$	${\displaystyle n\log n}$	1	No	Selección
Tipo de inserción	norte	${\displaystyle n^{2}}$	${\displaystyle n^{2}}$	1	sí	Inserción	O ( n + d ) , en el peor de los casos sobre secuencias que tienen d inversiones .
Orden de bloque	norte	${\displaystyle n\log n}$	${\displaystyle n\log n}$	1	sí	Inserción y fusión	Combinar un bloque basado ${\displaystyle O(n)}$algoritmo de fusión in situ [9] con una ordenación de fusión ascendente .
Quadsort	norte	${\displaystyle n\log n}$	${\displaystyle n\log n}$	norte	sí	Fusión	Utiliza una red de clasificación de 4 entradas . [10]
Timsort	norte	${\displaystyle n\log n}$	${\displaystyle n\log n}$	norte	sí	Inserción y fusión	Hace n-1 comparaciones cuando los datos ya están ordenados o ordenados al revés.
Orden de selección	${\displaystyle n^{2}}$	${\displaystyle n^{2}}$	${\displaystyle n^{2}}$	1	No	Selección	Estable con ${\displaystyle O(n)}$espacio adicional o cuando se utilizan listas vinculadas. [11]
Cubesort	norte	${\displaystyle n\log n}$	${\displaystyle n\log n}$	norte	sí	Inserción	Hace n-1 comparaciones cuando los datos ya están ordenados o ordenados al revés.
Shellsort	${\displaystyle n\log n}$	${\displaystyle n^{4/3}}$	${\displaystyle n^{3/2}}$	1	No	Inserción	Tamaño de código pequeño.
Ordenamiento de burbuja	norte	${\displaystyle n^{2}}$	${\displaystyle n^{2}}$	1	sí	Intercambiar	Diminuto tamaño de código.
Tipo de intercambio	${\displaystyle n^{2}}$	${\displaystyle n^{2}}$	${\displaystyle n^{2}}$	1	sí	Intercambiar	Diminuto tamaño de código.
Tipo de árbol	${\displaystyle n\log n}$	${\displaystyle n\log n}$	${\displaystyle n\log n}$(equilibrado)	norte	sí	Inserción	Cuando se utiliza un árbol de búsqueda binario autoequilibrado .
Orden de ciclo	${\displaystyle n^{2}}$	${\displaystyle n^{2}}$	${\displaystyle n^{2}}$	1	No	Selección	En el lugar con un número teóricamente óptimo de escrituras.
Orden de biblioteca	${\displaystyle n\log n}$	${\displaystyle n\log n}$	${\displaystyle n^{2}}$	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	${\displaystyle n\log n}$	${\displaystyle n\log n}$	norte	No	Inserción y selección	Encuentra todas las subsecuencias crecientes más largas en O ( n log n ) .
Smoothsort	norte	${\displaystyle n\log n}$	${\displaystyle n\log n}$	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	${\displaystyle n^{2}}$	${\displaystyle n^{2}}$	norte	sí	Selección
Tipo de torneo	${\displaystyle n\log n}$	${\displaystyle n\log n}$	${\displaystyle n\log n}$	n [12]	No	Selección	Variación del tipo de pila.
Tipo de coctelera	norte	${\displaystyle n^{2}}$	${\displaystyle n^{2}}$	1	sí	Intercambiar	Una variante de Bubblesort que trata bien con valores pequeños al final de la lista
Tipo de peine	${\displaystyle n\log n}$	${\displaystyle n^{2}}$	${\displaystyle n^{2}}$	1	No	Intercambiar	Más rápido que la clasificación de burbujas en promedio.
Tipo de gnomo	norte	${\displaystyle n^{2}}$	${\displaystyle n^{2}}$	1	sí	Intercambiar	Diminuto tamaño de código.
Desorganizar ordenación [13] [14]	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 [15]	norte	${\displaystyle n\log n}$	${\displaystyle n\log n}$	1	sí	?	Realiza O ( n ) movimientos de datos.
Tipo impar-par	norte	${\displaystyle n^{2}}$	${\displaystyle n^{2}}$	1	sí	Intercambiar	Se puede ejecutar fácilmente en procesadores paralelos.
Orden de círculo	${\displaystyle n\log n}$	${\displaystyle n\log ^{2}n}$	${\displaystyle n\log ^{2}n}$	1	No	Intercambiar	Mejor en ciertos tipos de insumos.

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 ) . ^{[16] Las} complejidades siguientes asumen n elementos a ordenar, con claves de tamaño k , tamaño de dígito d , y r el rango de números a ordenar. 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 la máquina de acceso aleatorio de costo unitario modelo, algoritmos con tiempo de ejecución de ${\displaystyle \scriptstyle n\cdot {\frac {k}{d}}}$, 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${\displaystyle 2^{\frac {k}{d}}}$, y una mayor cantidad de elementos para ordenar requeriría una k mayor para almacenarlos en la memoria. ^[17]

Clases sin comparación

Nombre	Mejor	Promedio	Peor	Memoria	Estable	n ≪ 2 k	Notas
Tipo de casillero	-	${\displaystyle n+2^{k}}$	${\displaystyle n+2^{k}}$	${\displaystyle 2^{k}}$	sí	sí	No se pueden ordenar los números no enteros.
Clasificación de cubos (llaves uniformes)	-	${\displaystyle n+k}$	${\displaystyle n^{2}\cdot k}$	${\displaystyle n\cdot k}$	sí	No	Supone una distribución uniforme de elementos del dominio en la matriz. [18] Tampoco puede ordenar números no enteros
Orden de depósito (claves de números enteros)	-	${\displaystyle n+r}$	${\displaystyle n+r}$	${\displaystyle n+r}$	sí	sí	Si r es${\displaystyle O(n)}$, entonces la complejidad del tiempo promedio es ${\displaystyle O(n)}$. [19]
Contando ordenar	-	${\displaystyle n+r}$	${\displaystyle n+r}$	${\displaystyle n+r}$	sí	sí	Si r es${\displaystyle O(n)}$, entonces la complejidad del tiempo promedio es ${\displaystyle O(n)}$. [18]
Clasificación de LSD Radix	${\displaystyle n}$	${\displaystyle n\cdot {\frac {k}{d}}}$	${\displaystyle n\cdot {\frac {k}{d}}}$	${\displaystyle n+2^{d}}$	sí	No	${\displaystyle {\frac {k}{d}}}$niveles de recursividad, 2 d para la matriz de recuento. [18] [19] 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.
Ordenar por radix MSD	-	${\displaystyle n\cdot {\frac {k}{d}}}$	${\displaystyle n\cdot {\frac {k}{d}}}$	${\displaystyle n+2^{d}}$	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)	-	${\displaystyle n\cdot {\frac {k}{1}}}$	${\displaystyle n\cdot {\frac {k}{1}}}$	${\displaystyle 2^{1}}$	No	No	d = 1 para en el lugar, ${\displaystyle k/1}$ niveles de recursividad, sin matriz de recuento.
Spreadsort	norte	${\displaystyle n\cdot {\frac {k}{d}}}$	${\displaystyle n\cdot \left({{\frac {k}{s}}+d}\right)}$	${\displaystyle {\frac {k}{d}}\cdot 2^{d}}$	No	No	Los asintóticos se basan en el supuesto de que n ≪ 2 k , pero el algoritmo no lo requiere.
Burstsort	-	${\displaystyle n\cdot {\frac {k}{d}}}$	${\displaystyle n\cdot {\frac {k}{d}}}$	${\displaystyle n\cdot {\frac {k}{d}}}$	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	${\displaystyle n+r}$	${\displaystyle n^{2}}$	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	-	${\displaystyle n\cdot {\frac {k}{d}}}$	${\displaystyle n\cdot {\frac {k}{d}}}$	${\displaystyle n+2^{d}}$	-	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.
Orden del sueño [20]	-	-	-	-	-	-	Para cada elemento, se crea una tarea separada que permanece inactiva durante un intervalo correspondiente a la clave de clasificación del elemento. Luego, los elementos se emiten y se recolectan secuencialmente en el tiempo.

Samplesort se puede utilizar 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	${\displaystyle n^{2}}$	N / A	No	Funciona solo con números enteros positivos. Requiere hardware especializado para su funcionamiento garantizado.${\displaystyle O(n)}$tiempo. Existe la posibilidad de implementación de software, pero el tiempo de ejecución será${\displaystyle O(S)}$, 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	${\displaystyle \log n}$	No	sí	El recuento es el número de volteretas.
Tipo de espagueti (encuesta)	norte	norte	norte	${\displaystyle n^{2}}$	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 # tipo espagueti .
Red de clasificación	Varía	Varía	Varía	Varía	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. [ disputado - discutir ]
Clasificador bitónico	${\displaystyle \log ^{2}n}$ paralelo	${\displaystyle \log ^{2}n}$ paralelo	${\displaystyle n\log ^{2}n}$ no paralelo	1	No	sí	Una variación eficaz de las redes de clasificación. [ disputado - discutir ]
Bogosort	norte	${\displaystyle (n\times n!)}$	ilimitado (cierto), ${\displaystyle (n\times n!)}$ (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. [21]
Tipo chiflado	${\displaystyle n^{\log 3/\log 1.5}}$	${\displaystyle n^{\log 3/\log 1.5}}$	${\displaystyle n^{\log 3/\log 1.5}}$	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 ... ) Puede estabilizarse y también es una red de clasificación .
Clasificación lenta	${\displaystyle n^{\log n}}$	${\displaystyle n^{\log n}}$	${\displaystyle n^{\log n}}$	norte	No	sí	Un algoritmo de multiplicar y entregar, antónimo del algoritmo de dividir y conquistar .

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. ^[22]
• Un algoritmo de ordenación de enteros aleatorios que toma${\displaystyle O\left(n{\sqrt {\log \log n}}\right)}$tiempo esperado y espacio O ( n ). ^[23]

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 ++ clasificar 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 la clasificación de bibliotecas, 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. 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 buen rendimiento en datos casi ordenados, y por lo tanto se prefiere en la práctica, pero la ordenación por selección usa menos escrituras y, por lo tanto, se usa cuando el rendimiento de escritura es un factor limitante.

Orden 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. ^[24] 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 ² ), 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. ^[25] 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 ² ). 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 tipo de combinación) o introsort (basado en clasificación rápida, recurriendo a clasificación 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. ^[26] 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 O ( n) complejidad espacial, 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 ^[27] y Java (a partir de JDK7 ^[28] ). . Merge sort en sí es la rutina estándar en Perl , ^[29] entre otros, y se ha utilizado en Java al menos desde 2000 en JDK1.3 . ^[30]

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 . ^[31] 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 una 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.

Clasificació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 . ^{[32] [33]} 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, por lo que 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 ² ); 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 ² ) 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 ). Encontrar la mediana, como por el Sin embargo, el algoritmo de selección de la mediana de las medianas es una operación O ( n ) en listas no ordenadas y, por lo tanto, exige una sobrecarga significativa con la ordenación. En la práctica, la elección de un pivote aleatorio casi con certeza produce un rendimiento de O ( n  log  n ).

Shellsort

Un tipo de Shell, diferente del tipo de burbuja en que mueve elementos a numerosas posiciones de intercambio .

Shellsort fue inventado por Donald Shell en 1959. ^[34] Mejora el ordenamiento por inserción al mover elementos fuera de orden en 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${\displaystyle O(kn)}$tiempo, donde k es la mayor distancia entre dos elementos fuera de lugar. Esto significa que, en general, funcionan en O ( n ² ), 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 ² ) a O ( n ^4/3 ) y Θ ( n log ² 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 .

Clasificación 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.

Clasificación de burbujas

Una clasificación de burbujas, un algoritmo de clasificación que recorre continuamente una lista, intercambiando elementos hasta que aparecen en el orden correcto.

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. ^[35] El tiempo promedio de este algoritmo y el desempeño en el peor de los casos es O ( n ²), por lo que rara vez se utiliza para ordenar 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.

^[36]

Peine ordenar

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. ^[37] 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. ( Conejos, valores grandes alrededor del comienzo de la lista, no representan 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 entre sí y, a continuación, reduciendo la distancia elegida hasta que funcione como un tipo 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.

Orden de intercambio

La clasificación de intercambio a veces se confunde con la clasificación de burbujas, aunque los algoritmos son de hecho distintos. ^{[38] [39] La} clasificación de intercambio funciona comparando el primer elemento con todos los elementos que están por encima de él, intercambiando donde 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 de burbujas de detectar en una pasada si la lista ya está ordenada, pero puede ser más rápido que la clasificación de burbujas por un factor constante (una pasada menos sobre los datos que se van a ordenar; la mitad de comparaciones totales) en situaciones en el peor de los casos. Como cualquier ordenamiento simple O ( n ² ), puede ser razonablemente rápido en conjuntos de datos muy pequeños, aunque en general el ordenamiento por inserción será más rápido.

Clasificación 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 Snecesita 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.

Ordenar por cubos

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.

Ordenación por 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 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 CPU speed), que, en comparación con la velocidad del disco, es prácticamente instantánea.

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". ^[40]

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. ^{[41] [42]}

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,dividir y conquistar ) o un lado (selección rápida, 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

1. "Conoce a las 'señoras del refrigerador' que programaron el ENIAC" . Hilo mental . 2013-10-13 . Consultado el 16 de junio de 2016 .
2. Lohr, Steve (17 de diciembre de 2001). "Frances E. Holberton, 84, programador informático temprano" . NYTimes . Consultado el 16 de diciembre de 2014 .
3. Demuth, Howard B. (1956). Clasificación electrónica de datos (tesis doctoral). Universidad Stanford. ProQuest 301940891 . 
4. 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
5. 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 .
6. Sedgewick, R. (1978). "Implementación de programas Quicksort". Comm. ACM . 21 (10): 847–857. doi : 10.1145 / 359619.359631 .
7. 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.
8. 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 .  
9. Kim, PD; Kutzner, A. (2008). Fusión estable in situ 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.
10. https://qiita.com/hon_no_mushi/items/92ff1a220f179b8d40f9
11. "CLASIFICACIÓN DE SELECCIÓN (Java, C ++) - Algoritmos y estructuras de datos" . www.algolist.net . Consultado el 14 de abril de 2018 .
12. http://dbs.uni-leipzig.de/skripte/ADS1/PDF4/kap4.pdf
13. Kagel, Art (noviembre de 1985). "Desorganizar, no del todo". Lenguaje informático . 2 (11).
14. http://dictionary.sensagent.com/UnShuffle%20sort/en-en/
15. 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 .
16. 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
17. Nilsson, Stefan (2000). "¿El algoritmo de clasificación más rápido?" . Dr. Dobb's .
18. 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.
19. Goodrich, Michael T .; Tamassia, Roberto (2002). "4.5 Clasificación por cubos y clasificación por radicales". 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.
20. "Algoritmos de clasificación / clasificación de sueño - Código Rosetta" . rosettacode.org . Consultado el 16 de junio de 2021 .
21. 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 .
22. 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 .
23. 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.
24. Wirth, Niklaus (1986), Algoritmos y estructuras de datos , Upper Saddle River, Nueva Jersey: Prentice-Hall, págs. 76–77, ISBN 978-0130220059
25. Wirth 1986 , págs. 79–80
26. Wirth 1986 , págs. 101-102
27. "Descripción original de Tim Peters de timsort" . python.org . Consultado el 14 de abril de 2018 .
28. "TimSort.java de OpenJDK" . java.net . Consultado el 14 de abril de 2018 .
29. "ordenar - perldoc.perl.org" . perldoc.perl.org . Consultado el 14 de abril de 2018 .
30. Combinar ordenación en Java 1.3 , Sun. Archivado el 4 de marzo de 2009 en la Wayback Machine.
31. Wirth 1986 , págs. 87–89
32. Wirth 1986 , p. 93
33. 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
34. 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 .
35. Wirth 1986 , págs. 81–82
36. "núcleo / grupos.c" . Consultado el 5 de mayo de 2012 .
37. 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 .
38. "Algoritmo de clasificación de intercambio" . Tutoriales de programación de CodingUnit . Consultado el 10 de julio de 2021 .
39. "Tipo de intercambio" . JavaBitsNotebook.com . Consultado el 10 de julio de 2021 .
40. "Definición de tipo de etiqueta de la enciclopedia de la revista PC" . www.pcmag.com . Consultado el 14 de abril de 2018 .
41. 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. 
42. Ellis Horowitz y Sartaj Sahni , Fundamentos de estructuras de datos , H. Freeman & Co., ISBN 0-7167-8042-9 . 

Lectura adicional

• 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.
• Una comparación de algoritmos de clasificación : ejecuta una serie de pruebas de 9 de los principales algoritmos de clasificación utilizando Python timeit y Google Colab.