Algoritmo de clasificación

En informática, un algoritmo de clasificación es un algoritmo que ordena los elementos de una lista. Los órdenes más utilizados son el orden numérico y el orden lexicográfico, ya sea ascendente o descendente. La clasificación eficiente es importante para optimizar la eficiencia de otros algoritmos (como los algoritmos de búsqueda y combinación) que requieren que los datos de entrada estén en listas ordenadas. La clasificación también suele ser útil para canonicalizar datos y producir resultados legibles por humanos.

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

1. La salida está en orden monotónico (cada elemento no es menor/más grande que el elemento anterior, según el pedido requerido).
2. La salida es una permutación (una reordenación, pero conservando todos los elementos originales) de la entrada.

Para lograr una eficacia ó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, quizás 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 estaba Betty Holberton, quien trabajó en ENIAC y UNIVAC. La ordenación de burbuja se analizó ya en 1956. Los algoritmos asintóticamente óptimos 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 ordenación de biblioteca 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 comparaciones n log n, donde n es el número de elementos en la matriz a ordenar). Los algoritmos que no se basan en comparaciones, como la ordenación por conteo, pueden tener un mejor rendimiento.

Los algoritmos de clasificación prevalecen en las clases introductorias de ciencias de la computación, donde la abundancia de algoritmos para el problema proporciona una introducción suave a una variedad de conceptos básicos de algoritmos, como la notación O grande, los algoritmos divide y vencerás, las estructuras de datos como montones y árboles binarios, algoritmos aleatorizados, análisis de los casos mejor, peor y promedio, compensaciones espacio-temporales y límites superior e inferior.

Ordenar arreglos pequeños de manera óptima (en la menor cantidad de comparaciones e intercambios) o rápido (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 se pueden clasificar por:

• Computacional complejidad
  • Mejor, peor y promedio de casos en términos del tamaño de la lista. Para algoritmos típicos de clasificación de serie, buen comportamiento es O(nlogn), con tipo paralelo en O(log²n), y el mal comportamiento es O(n²). El comportamiento ideal para un tipo de serie es O(n), pero esto no es posible en el caso promedio. Ordenación paralela óptima es O(log)n).
  • Trazos para algoritmos "en el lugar".
• Uso de memoria (y uso de otros recursos informáticos). En particular, algunos algoritmos de clasificación son "en el lugar". Strictly, an in-place kind needs only O(1) Memory beyond the items being ordered; sometimes O(log)n) memoria adicional se considera "en el lugar".
• Recursión: Algunos algoritmos son recursivos o no recursivos, mientras que otros pueden ser ambos (por ejemplo, fusionarse).
• Estabilidad: algoritmos de clasificación estables mantienen el orden relativo de registros con teclas iguales (es decir, valores).
• Ya sean o no un tipo de comparación. Un tipo de comparación examina los datos sólo comparando dos elementos con un operador de comparación.
• Método general: inserción, intercambio, selección, fusión, etc. Tipos de cambio incluyen tipo de burbuja y variedad rápida. Las clases de selección incluyen ciclo y heapsort.
• Si el algoritmo es serial o paralelo. El resto de esta discusión se concentra casi exclusivamente en algoritmos de serie y asume la operación en serie.
• Adaptabilidad: Si la prescindencia de la entrada afecta o no al tiempo de funcionamiento. Se sabe que los algoritmos que tienen en cuenta esto son adaptables.
• Online: Un algoritmo como Insertion Sort que está en línea puede ordenar un flujo constante de entrada.

Estabilidad

Un ejemplo de tipo estable en jugar cartas. Cuando las tarjetas están clasificadas por rango con un tipo estable, los dos 5s deben permanecer en el mismo orden en la salida ordenada que estaban originalmente en. Cuando se clasifican con un tipo no estable, los 5 pueden terminar en el orden opuesto en la salida ordenada.

Los algoritmos de clasificación estable clasifican elementos iguales en el mismo orden en que aparecen en la entrada. Por ejemplo, en el ejemplo de clasificación de cartas a la derecha, las cartas se clasifican por su rango y se ignora su palo. Esto permite la posibilidad de múltiples versiones diferentes ordenadas correctamente de la lista original. Los algoritmos de clasificación estable eligen uno de estos, de acuerdo con la siguiente regla: si dos elementos se comparan como iguales (como las dos cartas de 5), entonces se conservará su orden relativo, es decir, si uno 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 varias clasificaciones en el mismo conjunto de datos. Por ejemplo, digamos que los registros de los estudiantes que consisten en el nombre y la 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 ordenación inestable, es posible que la ordenación por sección cambie el orden de los nombres, lo que da como resultado una lista de estudiantes no alfabética.

De manera más formal, los datos que se ordenan se pueden representar como un registro o una tupla de valores, y la parte de los datos que se usa para ordenar se denomina clave. En el ejemplo de las cartas, las cartas se representan como un registro (rango, palo) y la clave es el rango. Un algoritmo de clasificación es estable si cada vez que hay dos registros R y S con la misma clave, y R aparece antes que S en la lista original, entonces R siempre aparecerá antes que S en la lista ordenada.

Cuando los elementos iguales son indistinguibles, como con números enteros, o más generalmente, cualquier dato donde el elemento completo es la clave, la estabilidad no es un problema. La estabilidad tampoco es un problema si todas las teclas 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 utilizando el orden de las entradas en la lista de entrada original como criterio de desempate. Sin embargo, recordar este orden puede requerir tiempo y espacio adicionales.

Una aplicación para algoritmos de clasificación estables es 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 (♥), picas (♠), y dentro de cada palo, las cartas están ordenadas por rango. Esto se puede hacer clasificando primero las cartas por rango (usando cualquier tipo) y luego haciendo una clasificación estable por palo:

Dentro de cada palo, el ordenamiento estable conserva el ordenamiento por rango que ya se hizo. Esta idea se puede extender a cualquier número de claves y se utiliza mediante ordenación radix. Se puede lograr el mismo efecto 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 estas tablas, n es la cantidad de registros que se ordenarán. Las columnas "Mejor", "Promedio" y "Peor" dar la complejidad del tiempo en cada caso, bajo el supuesto de que la longitud de cada clave es constante y, por lo tanto, que todas las comparaciones, intercambios y otras operaciones pueden realizarse en un tiempo constante. "Memoria" denota la cantidad de almacenamiento adicional que se necesita adicionalmente al utilizado por la propia lista, bajo la misma suposición. Los tiempos de ejecución y los requisitos de memoria enumerados están dentro de la notación O grande, por lo tanto, la base de los logaritmos no importa. La notación log² n significa (log n)².

Ordenes 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.

Comparison sorts

Name	Best	Average	Worst	Memory	Stable	Method	Other notes
Quicksort	${displaystyle nlog n}$	${displaystyle nlog n}$	${displaystyle n^{2}}$	${displaystyle log n}$	No	Partitioning	Quicksort is usually done in-place with O(log n) stack space.
Merge sort	${displaystyle nlog n}$	${displaystyle nlog n}$	${displaystyle nlog n}$	n	Yes	Merging	Highly parallelizable (up to O(log n) using the Three Hungarians' Algorithm).
In-place merge sort	—	—	${displaystyle nlog ^{2}n}$	1	Yes	Merging	Can be implemented as a stable sort based on stable in-place merging.
Introsort	${displaystyle nlog n}$	${displaystyle nlog n}$	${displaystyle nlog n}$	${displaystyle log n}$	No	Partitioning & Selection	Used in several STL implementations.
Heapsort	${displaystyle nlog n}$	${displaystyle nlog n}$	${displaystyle nlog n}$	1	No	Selection
Insertion sort	n	${displaystyle n^{2}}$	${displaystyle n^{2}}$	1	Yes	Insertion	O(n + d), in the worst case over sequences that have d inversions.
Block sort	n	${displaystyle nlog n}$	${displaystyle nlog n}$	1	Yes	Insertion & Merging	Combine a block-based ${displaystyle O(n)}$ in-place merge algorithm with a bottom-up merge sort.
Timsort	n	${displaystyle nlog n}$	${displaystyle nlog n}$	n	Yes	Insertion & Merging	Makes n-1 comparisons when the data is already sorted or reverse sorted.
Selection sort	${displaystyle n^{2}}$	${displaystyle n^{2}}$	${displaystyle n^{2}}$	1	No	Selection	Stable with ${displaystyle O(n)}$ extra space, when using linked lists, or when made as a variant of Insertion Sort instead of swapping the two items.
Cubesort	n	${displaystyle nlog n}$	${displaystyle nlog n}$	n	Yes	Insertion	Makes n-1 comparisons when the data is already sorted or reverse sorted.
Shellsort	${displaystyle nlog n}$	${displaystyle n^{4/3}}$	${displaystyle n^{3/2}}$	1	No	Insertion	Small code size.
Bubble sort	n	${displaystyle n^{2}}$	${displaystyle n^{2}}$	1	Yes	Exchanging	Tiny code size.
Exchange sort	${displaystyle n^{2}}$	${displaystyle n^{2}}$	${displaystyle n^{2}}$	1	No	Exchanging	Tiny code size.
Tree sort	${displaystyle nlog n}$	${displaystyle nlog n}$	${displaystyle nlog n}$(balanced)	n	Yes	Insertion	When using a self-balancing binary search tree.
Cycle sort	${displaystyle n^{2}}$	${displaystyle n^{2}}$	${displaystyle n^{2}}$	1	No	Selection	In-place with theoretically optimal number of writes.
Library sort	${displaystyle nlog n}$	${displaystyle nlog n}$	${displaystyle n^{2}}$	n	No	Insertion	Similar to a gapped insertion sort. It requires randomly permuting the input to warrant with-high-probability time bounds, which makes it not stable.
Patience sorting	n	${displaystyle nlog n}$	${displaystyle nlog n}$	n	No	Insertion & Selection	Finds all the longest increasing subsequences in O(n log n).
Smoothsort	n	${displaystyle nlog n}$	${displaystyle nlog n}$	1	No	Selection	An adaptive variant of heapsort based upon the Leonardo sequence rather than a traditional binary heap.
Strand sort	n	${displaystyle n^{2}}$	${displaystyle n^{2}}$	n	Yes	Selection
Tournament sort	${displaystyle nlog n}$	${displaystyle nlog n}$	${displaystyle nlog n}$	n	No	Selection	Variation of Heapsort.
Cocktail shaker sort	n	${displaystyle n^{2}}$	${displaystyle n^{2}}$	1	Yes	Exchanging	A variant of Bubblesort which deals well with small values at end of list
Comb sort	${displaystyle nlog n}$	${displaystyle n^{2}}$	${displaystyle n^{2}}$	1	No	Exchanging	Faster than bubble sort on average.
Gnome sort	n	${displaystyle n^{2}}$	${displaystyle n^{2}}$	1	Yes	Exchanging	Tiny code size.
Odd–even sort	n	${displaystyle n^{2}}$	${displaystyle n^{2}}$	1	Yes	Exchanging	Can be run on parallel processors easily.

Ordenaciones sin comparación

La siguiente tabla describe algoritmos de clasificación enteros y otros algoritmos de clasificación que no son tipos de comparación. Como tal, no se limitan a Ω (n log n). Las complejidades a continuación suponen n artículos a clasificar, con llaves de tamaño k, tamaño de dígitos d, y r el rango de números a clasificar. Muchos de ellos se basan en la suposición de que el tamaño clave es lo suficientemente grande que todas las entradas tienen valores clave únicos, y por lo tanto que n ≪ 2^k, donde ≪ significa "mucho menos que". En el modelo de máquina de acceso aleatorio, algoritmos con tiempo de funcionamiento ${displaystyle scriptstyle ncdot {frac {k} {d}}$, como el tipo de radio, todavía tomar tiempo proporcional a .n log n), porque n se limita a no ser más que ${displaystyle 2^{frac {k} {d}}$, y un mayor número de elementos para ordenar requeriría un mayor k para guardarlos en la memoria.

Tipos de no comparación

Nombre	Mejor	Promedio	peor	Memoria	Stable	n ≪ 2k	Notas
Pigeonhole tipo	—	${displaystyle No.$	${displaystyle No.$	${displaystyle 2^{k}$	Sí.	Sí.	No puede ordenar no-integers.
Algo de cubo (laves uniformes)	—	${displaystyle No.$	${displaystyle n^{2}cdot k}$	${displaystyle ncdot k}$	Sí.	No	Asume la distribución uniforme de elementos del dominio en el array. Tampoco puede ordenar no-integers
Algo de cubo (claves enteros)	—	${displaystyle No.$	${displaystyle No.$	${displaystyle No.$	Sí.	Sí.	Si r es ${displaystyle O(n)}$, entonces la complejidad promedio del tiempo es ${displaystyle O(n)}$.
Contando algo	—	${displaystyle No.$	${displaystyle No.$	${displaystyle No.$	Sí.	Sí.	Si r es ${displaystyle O(n)}$, entonces la complejidad promedio del tiempo es ${displaystyle O(n)}$.
LSD Radix Sort	${displaystyle n}$	${displaystyle ncdot {fnMicroc {k} {d}}$	${displaystyle ncdot {fnMicroc {k} {d}}$	${displaystyle n+2^{d}$	Sí.	No	${displaystyle {frac {k} {}}} {fnK}} {f}}} {f}}} {f}}} {fn}}}}$ niveles de recursión, 2d para contar array. A diferencia de la mayoría de los tipos de distribución, esto puede clasificar números de puntos flotantes, números negativos y más.
MSD Radix Sort	—	${displaystyle ncdot {fnMicroc {k} {d}}$	${displaystyle ncdot {fnMicroc {k} {d}}$	${displaystyle n+2^{d}$	Sí.	No	Versión estable utiliza un array externo de tamaño n para mantener todos los contenedores. Igual que la variante LSD, puede ordenar no-integers.
MSD Radix Sort (en el lugar)	—	${displaystyle ncdot {fnMicroc {k}{1}}$	${displaystyle ncdot {fnMicroc {k}{1}}$	${displaystyle 2^{1}$	No	No	d=1 para el lugar, ${displaystyle k/1}$ Niveles de recursión, sin matriz de conteo.
Spreadsort	n	${displaystyle ncdot {fnMicroc {k} {d}}$	${displaystyle ncdot left({frac {k}}}+d}right)}$	${fnK}cdot 2}}$	No	No	Los asintotic se basan en la suposición de que n ≪ 2k, pero el algoritmo no requiere esto.
Burstsort	—	${displaystyle ncdot {fnMicroc {k} {d}}$	${displaystyle ncdot {fnMicroc {k} {d}}$	${displaystyle ncdot {fnMicroc {k} {d}}$	No	No	Tiene mejor factor constante que radio para clasificar cuerdas. Aunque se basa un poco en detalles de cuerdas comúnmente encontradas.
Flashsort	n	${displaystyle No.$	${displaystyle n^{2}$	n	No	No	Requiere una distribución uniforme de elementos del dominio en el array para funcionar en tiempo lineal. Si la distribución es extremadamente segado entonces puede ir cuadrático si el tipo subyacente es cuadrático (por lo general es un tipo de inserción). La versión en el lugar no es estable.
Postman	—	${displaystyle ncdot {fnMicroc {k} {d}}$	${displaystyle ncdot {fnMicroc {k} {d}}$	${displaystyle n+2^{d}$	—	No	Una variación del tipo de cubo, que funciona muy similar a MSD Radix Sort. Específica para las necesidades de servicio post.

Samplesort se puede usar para paralelizar cualquiera de las ordenaciones que no son de comparación, mediante la distribución eficiente de los datos en varios depósitos y luego pasar la clasificación a varios procesadores, sin necesidad de fusionarse, ya que los depósitos ya están ordenados entre sí.

Otros

Algunos algoritmos son lentos en comparación con los mencionados anteriormente, como bogosort con tiempo de ejecución ilimitado y stooge sort que tiene O(n^{2.7) tiempo de ejecución. Estos tipos generalmente se describen con fines educativos para demostrar cómo se estima el tiempo de ejecución de los algoritmos. La siguiente tabla describe algunos algoritmos de clasificación que no son prácticos para el uso en la vida real en contextos de software tradicionales debido a un rendimiento extremadamente bajo o requisitos de hardware especializado.}

Nombre	Mejor	Promedio	peor	Memoria	Stable	Comparación	Otras notas
Bead especie	n	S	S	${displaystyle n^{2}$	—	No	Funciona sólo con números enteros positivos. Requiere hardware especializado para que funcione en garantía ${displaystyle O(n)}$ tiempo. Hay una posibilidad para la implementación de software, pero el tiempo de ejecución será ${displaystyle O(S)}$, donde S es la suma de todos los enteros a ser ordenados; en el caso de pequeños enteros, se puede considerar lineal.
Una tortita simple	—	${displaystyle n^{2}$	${displaystyle n^{2}$	${displaystyle log n}$	No	Sí.	El conde es número de volteretas.
"No puedo creer que pueda ordenar"	${displaystyle n^{2}$	${displaystyle n^{2}$	${displaystyle n^{2}$	1	No	Sí.	Notable principalmente para parecer una ejecución errónea de tipo Insertion Sort o Exchange Sort.
Spaghetti (Poll)	n	n	n	${displaystyle n^{2}$	Sí.	Polling	Este es un algoritmo analógico de tiempo lineal para ordenar una secuencia de elementos, que requiere O()n) espacio de pila, y el tipo es estable. Esto requiere n procesadores paralelos. Ver espaguetis tipo Analisis.
Red de clasificación	Variaciones	Variaciones	Variaciones	Variaciones	Varies (las redes de clasificación estable requieren más comparaciones)	Sí.	La orden de comparación se establece con antelación sobre la base de un tamaño de red fijo.
Ordenador Bitónico	${displaystyle log ^{2}n}$ paralelo	${displaystyle log ^{2}n}$ paralelo	${displaystyle nlog ^{2}n}$ no paralelo	1	No	Sí.	Una variación efectiva de redes de clasificación.
Bogosort	n	${displaystyle (ntimes n!)}$	sin límites (certain), ${displaystyle (ntimes n!)}$ (esperada)	1	No	Sí.	Aleatorio. Utilizado sólo para propósitos de ejemplo, ya que incluso el mejor tiempo de ejecución esperado es horrible.
Algo así.	${displaystyle n^{log 3/log 1.5}$	${displaystyle n^{log 3/log 1.5}$	${displaystyle n^{log 3/log 1.5}$	n	No	Sí.	Más lento que la mayoría de los algoritmos de clasificación (incluso los ingenuos) con una complejidad del tiempo O()nlog 3 / log 1.5 ) O()n2.7095...) Puede ser estable, y también es una red de clasificación.
Slowsort	${displaystyle n^{log} No.$	${displaystyle n^{log} No.$	${displaystyle n^{log} No.$	n	No	Sí.	Un algoritmo de multiplicación y entrega, anónimo de algoritmo de división y conquista.

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 aleatorizado para clasificar las claves de un dominio de tamaño finito, tomando O()n log n) tiempo y tiempo O()nEl espacio.
• Un algoritmo de clasificación de enteros al azar ${displaystyle Oleft(n{sqrt {log log n}right)}$ tiempo previsto y O()nEl espacio.
• Uno de los autores del algoritmo mencionado anteriormente afirma también haber descubierto un algoritmo tomando ${displaystyle Oleft(n{sqrt {log n}right)}$ tiempo y tiempo O()nEl espacio, clasificando números reales. Afirmando además que, sin ninguna hipótesis adicional sobre la entrada, puede modificarse para lograr ${displaystyle Oleft(nlog n/{sqrt {log log n}right)}$ tiempo y tiempo O()nEl espacio.

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 clasificación por inserción se usa ampliamente para conjuntos de datos pequeños, mientras que para conjuntos de datos grandes se usa una clasificación asintóticamente eficiente, principalmente clasificación heapsort, merge sort o quicksort. Las implementaciones eficientes generalmente usan un algoritmo híbrido, que combina un algoritmo asintóticamente eficiente para la ordenación general con una ordenación por inserción para listas pequeñas en la parte inferior de una recursividad. Las implementaciones altamente optimizadas usan variantes más sofisticadas, como Timsort (clasificación por fusión, clasificación por inserción y lógica adicional), que se usa en Android, Java y Python, e introsort (clasificación rápida y clasificación en montón), que se usa (en formas variantes) en algunas clasificaciones de C++ implementaciones y en.NET.

Para datos más restringidos, como números en un intervalo fijo, se utilizan ampliamente clasificaciones de distribución como la clasificación por conteo o la clasificación por base. El tipo de burbuja y las variantes rara vez se usan en la práctica, pero se encuentran comúnmente en la enseñanza y las discusiones teóricas.

Al clasificar objetos físicamente (como alfabetizar documentos, exámenes o libros), las personas generalmente usan intuitivamente clasificaciones por inserción para conjuntos pequeños. Para conjuntos más grandes, las personas suelen clasificar primero, por ejemplo, por letra inicial, y la clasificación múltiple permite la clasificación práctica de conjuntos muy grandes. A menudo, el espacio es relativamente económico, por ejemplo, al distribuir objetos en el suelo o en un área grande, pero las operaciones son costosas, en particular mover un objeto a una gran distancia; la localidad de referencia es importante. Las ordenaciones por combinación también son prácticas para los objetos físicos, particularmente porque se pueden usar dos manos, una para cada lista que se va a combinar, mientras que otros algoritmos, como la ordenación heapsort o la ordenación rápida, no son adecuadas para el uso humano. Otros algoritmos, como la clasificación por biblioteca, una variante de la clasificación por inserción que deja espacios, también son prácticos para uso físico.

Ordenaciones simples

Dos de las ordenaciones más simples son la ordenación por inserción y la ordenación por selección, las cuales son eficientes con datos pequeños, debido a la baja sobrecarga, pero no son eficientes con 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.

Ordenar por inserción

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 como ponemos dinero en nuestra billetera. En las matrices, la nueva lista y los elementos restantes pueden compartir el espacio de la matriz, pero la inserción es costosa y requiere cambiar todos los elementos siguientes de uno en uno. Shellsort es una variante de ordenación por inserción que es más eficiente para listas más grandes.

Ordenación por selección

Ordenación por selección es una ordenación por comparación en el lugar. Tiene una complejidad O(n²), lo que lo hace ineficiente en listas grandes y, en general, funciona peor que el tipo de inserción similar. La ordenación por selección se destaca por su simplicidad y también tiene ventajas de rendimiento sobre algoritmos más complicados en ciertas 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. No hace más que n intercambios y, por lo tanto, es útil cuando el intercambio es muy costoso.

Clasificación eficiente

Los algoritmos de clasificación generales prácticos casi siempre se basan en un algoritmo con una complejidad de tiempo promedio (y generalmente la complejidad del peor de los casos) O(n log n), del cual el los más comunes son heapsort, merge sort y quicksort. Cada uno tiene ventajas y desventajas, siendo la más importante que la implementación simple de la ordenación por combinación usa O(n) espacio adicional, y la implementación simple de la ordenación rápida tiene O(n²) complejidad en el peor de los casos. Estos problemas se pueden resolver o mejorar a costa de un algoritmo más complejo.

Si bien estos algoritmos son asintóticamente eficientes en datos aleatorios, para lograr una eficiencia 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 ordenar en tiempo O(n) mediante algoritmos apropiados. Finalmente, también pueden ser inestables, y la estabilidad es a menudo una propiedad deseable en cierto modo. Por lo tanto, a menudo se emplean algoritmos más sofisticados, como Timsort (basado en la ordenación por combinación) o introsort (basado en la ordenación rápida, recurriendo a la ordenación en montón).

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 debe ir después del segundo. Luego fusiona cada una de las listas resultantes de dos en listas de cuatro, luego fusiona esas listas de cuatro, y así sucesivamente; hasta que al menos dos listas se fusionen en la lista ordenada final. De los algoritmos descritos aquí, este es el primero que escala bien a listas muy grandes, porque su tiempo de ejecución en el peor de los casos es O(n log n). También se aplica fácilmente a listas, no solo a matrices, ya que solo requiere acceso secuencial, no acceso aleatorio. Sin embargo, tiene una complejidad adicional de espacio O(n) e involucra una gran cantidad de copias en implementaciones simples.

La ordenación por combinación ha experimentado un aumento relativamente reciente en la popularidad de las implementaciones prácticas, debido a su uso en el algoritmo sofisticado Timsort, que se usa para la rutina de ordenación estándar en los lenguajes de programación Python y Java (a partir de JDK7). Merge sort en sí mismo es la rutina estándar en Perl, entre otros, y se ha utilizado en Java al menos desde 2000 en JDK1.3.

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, luego continúa 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. Una vez que la lista de datos se ha convertido en un montón, se garantiza que el nodo raíz sea 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 requiere un tiempo de O(log n), en lugar de O(n) para una exploración lineal como en la ordenación por selección simple. Esto permite que Heapsort se ejecute en tiempo O(n log n), y esta es también la complejidad del peor de los casos.

Ordenación rápida

Quicksort es un algoritmo divide y vencerás que se basa en una operación de partición: para particionar una matriz, un elemento llamado pivote es seleccionado. Todos los elementos más pequeños que el pivote se mueven antes que él y todos los elementos más grandes se mueven después. Esto se puede hacer de manera eficiente en tiempo lineal y en el lugar. Las sublistas mayor y menor se ordenan recursivamente. Esto produce una complejidad de tiempo promedio de O(n log n), con una sobrecarga baja y, por lo tanto, este es un algoritmo popular. Las implementaciones eficientes de clasificación rápida (con partición en el lugar) 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 Quicksort es que su rendimiento en el peor de los casos es O(n²); Si bien 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 Quicksort es, por lo tanto, elegir un buen elemento pivote, ya que las malas elecciones de pivotes pueden resultar en un rendimiento O(n²) drásticamente más lento, pero una buena elección de pivots produce un rendimiento O(n log n), que es asintóticamente óptimo. Por ejemplo, si en cada paso se elige la mediana como pivote, 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 ordenadas y, por lo tanto, exige una sobrecarga significativa con la clasificación. En la práctica, es casi seguro que elegir un pivote aleatorio produce un rendimiento O(n log n).

Si una garantía de O(n log n) el rendimiento es importante, hay una simple modificación para lograr eso. La idea, debido a Musser, es establecer un límite en la profundidad máxima de la recursión. Si ese límite es superado, entonces la clasificación continúa utilizando el algoritmo de heapsort. Musser propuso que el límite debería ser ${displaystyle 1+2lfloor log _{2}(n)rfloor }$, que es aproximadamente el doble de la profundidad máxima de recursión uno esperaría en promedio con una matriz ordenada al azar.

Clasificación de conchas

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

Shellsort fue inventado por Donald Shell en 1959. Mejora al tipo de inserción al salir de los elementos de orden más de una posición a la vez. El concepto detrás de Shellsort es que tipo de inserción funciona en ${displaystyle O(kn)}$ tiempo, donde k es la mayor distancia entre dos elementos fuera de lugar. Esto significa que generalmente, realizan en O()n²), pero para datos que se clasifican mayormente, con sólo unos pocos elementos fuera de lugar, realizan más rápido. Por lo tanto, al clasificar los elementos lejos, y reducir progresivamente la brecha entre los elementos para ordenar, el tipo final computa mucho más rápido. Una implementación se puede describir como la organización de la secuencia de datos en un array bidimensional y luego clasificar las columnas del array utilizando el tipo de inserción.

La complejidad de tiempo en el peor de los casos de Shellsort es un problema abierto y depende de la secuencia de brecha utilizada, con complejidades conocidas que van desde O(n^{2< /sup>) a O(n4/3) y Θ(n log2< /sup> n). Esto, combinado con el hecho de que Shellsort está en el lugar, solo necesita una cantidad de código relativamente pequeña y no requiere el uso de la pila de llamadas, hace que sea útil en situaciones donde la memoria es escasa, como en sistemas integrados. y núcleos del sistema operativo.}

Tipo de burbuja y variantes

La clasificación de burbuja y variantes como la clasificación de peine y la clasificación de cóctel son algoritmos de clasificación simples y muy ineficientes. Se ven con frecuencia en textos introductorios debido a la facilidad de análisis, pero rara vez se usan en la práctica.

Ordenación de burbujas

Una especie de burbuja, un algoritmo de clasificación que pasa continuamente a través de una lista, intercambiando artículos hasta que aparezcan en el orden correcto.

La clasificación de burbujas es un algoritmo de clasificación simple. El algoritmo comienza al principio del conjunto de datos. Compara los dos primeros elementos, y si el primero es mayor que el segundo, los intercambia. Continúa haciendo esto para cada par de elementos adyacentes hasta el final del conjunto de datos. Luego comienza de nuevo con los primeros dos elementos, repitiendo hasta que no se hayan producido intercambios en el último pase. El tiempo promedio de este algoritmo y el rendimiento en el peor de los casos es O(n²), por lo que rara vez se usa para ordenar grandes conjuntos de datos 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 ordenación por 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 por una sola posición (por ejemplo, 0123546789 y 1032547698), el intercambio de clasificación de burbuja los pondrá en orden en el primer paso, el segundo paso encontrará todos los elementos en orden, por lo que la clasificación tomará solo 2n tiempo.

Clasificación de peine

Comb sort es un algoritmo de clasificación relativamente simple basado en bubble sort y diseñado originalmente por Włodzimierz Dobosiewicz en 1980. 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 eliminar las tortugas, o valores pequeños cerca del final de la lista, ya que en una clasificación de burbuja estos ralentizan la clasificación enormemente. (Conejos, valores grandes alrededor del comienzo de la lista, no plantean un problema en la ordenación de burbujas) Lo logra intercambiando inicialmente elementos que están a cierta distancia entre sí en la matriz, en lugar de solo intercambiando elementos si están adyacentes 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 ordenación por inserción que intercambia elementos espaciados a cierta distancia entre sí, se puede pensar en la ordenación en peine como la misma generalización aplicada a la ordenación en burbuja.

Clasificación de intercambio

Exchange sort a veces se confunde con bubble sort, aunque, de hecho, los algoritmos son distintos. La ordenación por intercambio funciona comparando el primer elemento con todos los elementos por encima de él, intercambiando cuando sea necesario, lo que garantiza 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ápida que la clasificación de burbujas por un factor constante (una pasada menos sobre los datos a clasificar; la mitad de comparaciones totales) en peores situaciones. Como cualquier clasificación O(n²) simple, puede ser razonablemente rápida en conjuntos de datos muy pequeños, aunque en general la clasificación por inserción será más rápida.

Clasificación de distribución

Ordenación por 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 la ordenación por depósito como la ordenación por flash son algoritmos de ordenación basados en la distribución. Los algoritmos de clasificación de distribución se pueden usar en un solo procesador, o pueden ser un algoritmo distribuido, donde los subconjuntos individuales se clasifican por separado en diferentes procesadores y luego se combinan. Esto permite la clasificación externa de datos demasiado grandes para caber en la memoria de una sola computadora.

Orden de conteo

La ordenación por conteo es aplicable cuando se sabe que cada entrada pertenece a un conjunto particular, S, de posibilidades. El algoritmo se ejecuta en tiempo O(|S| + n) y memoria O(|S|) donde n es la longitud de la entrada. Funciona creando una matriz de enteros de tamaño |S| y usar el contenedor ith para contar las ocurrencias del miembro ith de S en la entrada. Luego, cada entrada se cuenta incrementando el valor de su contenedor correspondiente. Luego, la matriz de conteo se recorre para organizar todas las entradas en orden. Este algoritmo de clasificación a menudo no se puede usar porque S debe 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 aumenta n. También se puede modificar para proporcionar un comportamiento estable.

Ordenar cubo

La ordenación por cubos es un algoritmo de clasificación tipo divide y vencerás que generaliza la ordenación por conteo mediante la partición de una matriz en un número finito de cubos. Luego, cada depósito se clasifica individualmente, ya sea utilizando un algoritmo de clasificación diferente o aplicando recursivamente el algoritmo de clasificación de depósitos.

Una ordenación por categorías funciona mejor cuando los elementos del conjunto de datos se distribuyen uniformemente en todas las categorías.

Ordenación Radix

Radix sort 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 tiempo O(n · k). Radix sort 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 conserva su orden relativo usando una ordenación estable. Luego los ordena por el siguiente dígito, y así sucesivamente desde el menos significativo hasta el más significativo, finalizando con una lista ordenada. Mientras que la ordenación radix LSD requiere el uso de una ordenación estable, el algoritmo de ordenación radix MSD no lo requiere (a menos que se desee una ordenación estable). La ordenación radix de MSD in situ no es estable. Es común que el algoritmo de ordenación por conteo sea utilizado internamente por la ordenación 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 radix.

Patrones de uso de memoria y clasificación de índices

Cuando el tamaño de la matriz que se va a clasificar se aproxima o supera la memoria principal disponible, por lo que se debe emplear espacio de intercambio o disco (mucho más lento), el patrón de uso de memoria de un algoritmo de clasificación se vuelve importante y un algoritmo que podría han sido bastante eficientes 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 las secciones de memoria deben copiarse o intercambiarse hacia y desde el disco puede dominar las características de rendimiento de un algoritmo. Por lo tanto, la cantidad de pases y la localización de las comparaciones pueden ser más importantes que la cantidad bruta 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 virtualmente instantáneo.

Por ejemplo, el popular algoritmo recursivo de clasificación rápida proporciona un rendimiento bastante razonable con una RAM adecuada, pero debido a la forma recursiva en que copia partes de la matriz, se vuelve mucho menos práctico cuando la matriz no cabe en la RAM, ya que puede causar una serie de operaciones lentas de copia o movimiento hacia y desde el disco. En ese escenario, puede ser preferible otro algoritmo incluso si requiere más comparaciones totales.

Una forma de solucionar este problema, que funciona bien cuando se ordenan registros complejos (como en una base de datos relacional) por un campo clave relativamente pequeño, es crear un índice en la matriz y luego ordenar el índice, en lugar de que toda la matriz. (Una versión ordenada de la matriz completa se puede producir con una sola pasada, leyendo el índice, pero a menudo incluso eso es innecesario, ya que tener el índice ordenado es adecuado). Debido a que el índice es mucho más pequeño que la matriz completa, puede encaja fácilmente en la memoria donde no cabría la matriz completa, lo que elimina efectivamente el problema de intercambio de discos. Este procedimiento a veces se denomina "clasificación de etiquetas".

Otra técnica para superar el problema del tamaño de la memoria es usar la clasificación externa, por ejemplo, una de las formas es combinar dos algoritmos de manera que aproveche la fortaleza de cada uno para mejorar el rendimiento general. Por ejemplo, la matriz se puede subdividir en fragmentos de un tamaño que quepa en la RAM, el contenido de cada fragmento se ordena mediante un algoritmo eficiente (como clasificación rápida) y los resultados se fusionan mediante un k- combinación de manera similar a la utilizada en la ordenación por combinación. Esto es más rápido que realizar una ordenación por fusión o una ordenación rápida en toda la lista.

También se pueden combinar técnicas. Para clasificar conjuntos de datos muy grandes que superan con creces la memoria del sistema, es posible que incluso el índice deba clasificarse mediante un algoritmo o una combinación de algoritmos diseñados para funcionar razonablemente con la memoria virtual, es decir, para reducir la cantidad de intercambio necesario.

Algoritmos relacionados

Los problemas relacionados incluyen clasificación aproximada (clasificar una secuencia dentro de una cierta cantidad del orden correcto), clasificación parcial (clasificar solo los k elementos más pequeños de una lista o encontrar el k elementos más pequeños, pero desordenados) y 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, a menudo derivados de la generalización de un algoritmo de clasificación. El ejemplo más notable es quickselect, que está relacionado con quicksort. Por el contrario, algunos algoritmos de clasificación pueden obtenerse mediante la aplicación repetida de un algoritmo de selección; quicksort y quickselect se pueden ver como el mismo movimiento de pivote, que difieren solo en si uno recurre en ambos lados (quicksort, divide y vencerás) o en un lado (quickselect, reduce-and-conquer).

Un tipo 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. El barajado 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 conocido algoritmo simple y eficiente para barajar: el barajado de Fisher-Yates.

Los algoritmos de clasificación son ineficaces para encontrar un pedido en muchas situaciones. Por lo general, cuando los elementos no tienen una función de comparación confiable (preferencias colaborativas como sistemas de votación), las comparaciones son muy costosas (deportes) o cuando sería imposible comparar todos los elementos por pares para todos los criterios (motores de búsqueda). En estos casos, el problema suele denominarse clasificación y el objetivo es encontrar el "mejor" resultado para algunos criterios de acuerdo con las probabilidades inferidas de comparaciones o clasificaciones. Un ejemplo común es el ajedrez, donde los jugadores se clasifican con el sistema de calificación Elo y las clasificaciones están determinadas por un sistema de torneo en lugar de un algoritmo de clasificación.