Algoritmo de ordenación

En informática , un algoritmo de ordenación es aquel que ordena los elementos de una lista . Los órdenes más comunes son el numérico y el lexicográfico , ya sea ascendente o descendente. Una ordenación eficiente es fundamental para optimizar el rendimiento de otros algoritmos (como los de búsqueda y fusión ) que requieren que los datos de entrada estén en listas ordenadas. La ordenación también suele ser útil para normalizar datos y generar resultados legibles.

Formalmente, el resultado de cualquier algoritmo de ordenación debe satisfacer dos condiciones:

La salida se presenta en orden monótono (cada elemento no es menor ni mayor que el elemento anterior, según el orden requerido).
El resultado es una permutación (una reordenación, pero conservando todos los elementos originales) de la entrada.

Aunque algunos algoritmos están diseñados para el acceso secuencial , los algoritmos de mayor rendimiento asumen que los datos se almacenan en una estructura de datos que permite el acceso aleatorio .

Historia y conceptos

Desde los inicios de la informática, el problema de la ordenación ha atraído mucha investigación, quizás debido a la complejidad de resolverlo de manera eficiente a pesar de su enunciado simple y familiar. Entre los autores de los primeros algoritmos de ordenación alrededor de 1951 se encontraba Betty Holberton , quien trabajó en ENIAC y UNIVAC . ^{[ 1 ]}^{[ 2 ]} El algoritmo de ordenación de burbuja se analizó ya en 1956. ^{[ 3 ]} Los algoritmos asintóticamente óptimos se conocen desde mediados del siglo XX ; aún se siguen inventando nuevos algoritmos, como el ampliamente utilizado Timsort, que data de 2002, y el algoritmo de ordenación de biblioteca, que se publicó por primera vez en 2006.

Los algoritmos de ordenación por comparación tienen un requisito fundamental de $n\log {n}-1.4427n+O(\log {n})$ comparaciones. Los algoritmos que no se basan en comparaciones, como el ordenamiento por conteo , pueden tener un mejor rendimiento.

Los algoritmos de ordenación son frecuentes en los cursos introductorios de informática , donde la abundancia de algoritmos para este problema proporciona una introducción sencilla a diversos conceptos algorítmicos fundamentales, como la notación O grande , los algoritmos de divide y vencerás , las estructuras de datos como los montículos y los árboles binarios , los algoritmos aleatorios , el análisis del mejor, el peor y el caso promedio , las compensaciones entre tiempo y espacio , y los límites superiores e inferiores .

La ordenación óptima (con el menor número de comparaciones e intercambios) o rápida (teniendo en cuenta las particularidades de la máquina) de matrices pequeñas sigue siendo un problema de investigación abierto, con soluciones conocidas únicamente para matrices muy pequeñas (menos de 20 elementos). De forma similar, la ordenación óptima (según diversas definiciones) en una máquina paralela es un tema de investigación abierto.

Clasificación

Los algoritmos de ordenación se pueden clasificar de la siguiente manera:

Complejidad computacional
- Comportamiento en el mejor, peor y promedio caso en términos del tamaño de la lista. Para los algoritmos de ordenación serial típicos, el buen comportamiento es O( n log n ), con ordenación paralela en O(log ²n ), y el mal comportamiento es O( n ² ). El comportamiento ideal para una ordenación serial es O( n ), pero esto no es posible en el caso promedio. La ordenación paralela óptima es O(log n ).
- Intercambios para algoritmos "in situ".
Uso de memoria (y uso de otros recursos informáticos). En particular, algunos algoritmos de ordenación son " in situ ". Estrictamente hablando, una ordenación in situ solo necesita O(1) de memoria más allá de los elementos que se ordenan; a veces , se considera "in situ" una memoria adicional de O(log n ).
Recursión: Algunos algoritmos son típicamente recursivos o típicamente no recursivos, mientras que otros pueden ser típicamente ambas cosas (por ejemplo, ordenación por fusión).
Estabilidad: los algoritmos de ordenación estables mantienen el orden relativo de los registros con claves (es decir, valores) iguales.
Independientemente de si se trata de un algoritmo de ordenación por comparación . Un algoritmo de ordenación por comparación examina los datos únicamente comparando dos elementos con un operador de comparación.
Método general: inserción, intercambio, selección, fusión, etc. Los algoritmos de ordenación por intercambio incluyen el ordenamiento de burbuja y el ordenamiento rápido. Los algoritmos de ordenación por selección incluyen el ordenamiento cíclico y el ordenamiento por montículos.
Ya sea que el algoritmo sea serial o paralelo. El resto de esta discusión se centra casi exclusivamente en algoritmos seriales y presupone su funcionamiento en serie.
Adaptabilidad: Si el ordenamiento previo de la entrada afecta o no al tiempo de ejecución. Se sabe que los algoritmos que tienen esto en cuenta son adaptativos .
En línea: Un algoritmo como el de ordenación por inserción que se ejecuta en línea puede ordenar un flujo constante de datos de entrada.

Estabilidad

Los algoritmos de ordenación estable ordenan los elementos iguales en el mismo orden en que aparecen en la entrada. Por ejemplo, en el ejemplo de ordenación de cartas de la derecha, las cartas se ordenan según su rango, sin tener en cuenta su palo. Esto permite la posibilidad de obtener varias versiones correctas de la lista original. Los algoritmos de ordenación estable eligen una de ellas según la siguiente regla: si dos elementos son iguales (como las dos cartas del 5), se conserva su orden relativo; es decir, si uno aparece antes que el otro en la entrada, aparecerá antes que el otro en la salida.

La estabilidad es importante para preservar el orden en múltiples ordenamientos del mismo conjunto de datos . Por ejemplo, supongamos que los registros de estudiantes, que constan de nombre y sección de clase, se ordenan dinámicamente, primero por nombre y luego por sección de clase. Si se utiliza un algoritmo de ordenamiento estable en ambos casos, la ordenación por sección de clase no alterará el orden de los nombres; con un algoritmo de ordenamiento inestable, la ordenación por sección podría desordenar el orden de los nombres, lo que resultaría en una lista de estudiantes no alfabética.

De forma más formal, los datos que se ordenan pueden representarse como un registro o tupla de valores, y la parte de los datos que se utiliza para la ordenación se denomina clave . En el ejemplo de las cartas, estas se representan como un registro (rango, palo), y la clave es el rango. Un algoritmo de ordenación es estable si, siempre que existan 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 en el caso de los números enteros, o, en general, en cualquier dato donde el elemento completo sea la clave, la estabilidad no representa un problema. La estabilidad tampoco es un problema si todas las claves son diferentes.

Los algoritmos de ordenación inestables pueden implementarse de forma especial para que sean estables. Una manera de lograrlo es extender artificialmente la comparación de claves, de modo que las comparaciones entre dos objetos con claves idénticas 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 de los algoritmos de ordenación estable es la ordenación de listas mediante claves primaria y secundaria. Por ejemplo, supongamos que queremos ordenar una mano de cartas de forma 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 lograr ordenando primero las cartas por rango (con cualquier algoritmo de ordenación) y luego realizando una ordenación estable por palo:

Dentro de cada palo, la ordenación estable conserva el orden por rango previamente establecido. Esta idea puede extenderse a cualquier número de claves y es utilizada por la ordenación por radix . El mismo efecto puede lograrse con una ordenación inestable mediante una comparación de claves lexicográficas, que, por ejemplo, compara primero por palo y luego por rango si los palos son iguales.

Comparación de algoritmos

Este análisis parte del supuesto de que la longitud de cada clave es constante y que todas las comparaciones, intercambios y demás operaciones pueden realizarse en tiempo constante.

Leyenda:

$n$ es el número de registros que se van a ordenar.
La columna de comparación tiene las siguientes clasificaciones: "Mejor", "Promedio" y "Peor" si se proporciona la complejidad temporal para cada caso.
"Memoria" indica la cantidad de almacenamiento adicional que requiere el algoritmo.
Los tiempos de ejecución y los requisitos de memoria que se indican están en notación Big O , por lo que la base de los logaritmos no importa.
La notación $log 2 n$ significa $(log n) 2$ .

Clasificación por comparación

A continuación se muestra una tabla de ordenamientos por comparación . El análisis matemático demuestra que un ordenamiento por comparación no puede tener un rendimiento mejor que $O (n log n)$ en promedio. ^{[ 4 ]}

Clasificación sin comparación

La siguiente tabla describe algoritmos de ordenación de enteros y otros algoritmos de ordenación que no son de ordenación por comparación . Estos algoritmos no se limitan a Ω ( n log n ) a menos que cumplan con el modelo de máquina de acceso aleatorio de costo unitario , como se describe a continuación. ^{[ 9 ]}

Las complejidades que se describen a continuación suponen que se deben ordenar $n elementos, con claves de tamaño$ $k$ , tamaño de dígito $d$ y $r$ el rango de números que se van 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, que $n ≪ 2 k$ , donde $≪$ significa "mucho menor que".
En el modelo de máquina de acceso aleatorio de costo unitario , los algoritmos con tiempo de ejecución de $n\cdot {\frac {k}{d}}$ , como el ordenamiento por radix, todavía requieren un tiempo proporcional a $Θ(n log n)$ , porque $n$ está limitado a no ser mayor que $2^{\frac {k}{d}}$ y un mayor número de elementos para ordenar requeriría un $k$ mayor para poder almacenarlos en la memoria. ^{[ 10 ]}

Samplesort se puede utilizar para paralelizar cualquiera de los algoritmos de ordenación que no sean de comparación, distribuyendo eficientemente los datos en varios grupos y luego pasando la ordenación a varios procesadores, sin necesidad de fusionarlos, ya que los grupos ya están ordenados entre sí.

Otros

Algunos algoritmos son lentos en comparación con los mencionados anteriormente, como el bogosort ^, cuyo tiempo de ejecución es ilimitado, y el stooge sort , cuyo tiempo de ejecución es O ( n².⁷ ). Estos algoritmos se suelen describir con fines didácticos para demostrar cómo se estima su tiempo de ejecución. La siguiente tabla describe algunos algoritmos de ordenación que resultan poco prácticos para su uso en entornos de software tradicionales debido a su rendimiento extremadamente bajo o a los requisitos de hardware especializados que requieren.

Los científicos informáticos teóricos han inventado otros algoritmos de ordenación que proporcionan una complejidad temporal mejor que O ( n log n ) asumiendo ciertas restricciones, entre las que se incluyen:

El algoritmo de Thorup, ^{[ 14 ]} un algoritmo de ordenación aleatoria de enteros , que toma $O (n log log n)$ tiempo y O ( n ) espacio. ^{[ 14 ]}
Algoritmo AHNR, ^{[ 15 ]} un algoritmo de ordenación de enteros que se ejecuta en $O(n\log \log n)$ el tiempo de forma determinista, y también tiene una versión aleatoria que se ejecuta en tiempo lineal cuando las palabras son lo suficientemente largas, específicamente $w\geq (\log n)^{2+\varepsilon }$ (donde w es el tamaño de la palabra).
Un algoritmo de ordenación de enteros aleatorios que toma $O\left(n{\sqrt {\log \log n}}\right)$ tiempo esperado y espacio O ( n ). ^{[ 16 ]}

Algoritmos de ordenación populares

Aunque existen numerosos algoritmos de ordenación, en las implementaciones prácticas predominan algunos. La ordenación por inserción se utiliza ampliamente para conjuntos de datos pequeños, mientras que para conjuntos de datos grandes se emplea una ordenación asintóticamente eficiente, principalmente heapsort, merge sort o quicksort. Las implementaciones eficientes suelen utilizar un algoritmo híbrido , que combina un algoritmo asintóticamente eficiente para la ordenación general con la ordenación por inserción para listas pequeñas en la parte inferior de una recursión. Las implementaciones altamente optimizadas utilizan variantes más sofisticadas, como Timsort (merge sort, insertion sort y lógica adicional), utilizado en Android , Java y Python , e introsort (quicksort y heapsort), utilizado (en variantes) en algunas implementaciones de ordenación de C++ y en .NET .

Para datos más restringidos, como números en un intervalo fijo, se utilizan ampliamente algoritmos de ordenación por distribución , como la ordenación por conteo o la ordenación por radix. La ordenación de burbuja y sus variantes se utilizan raramente en la práctica, pero son comunes en la enseñanza y en debates teóricos.

Al ordenar físicamente objetos (como papeles, exámenes o libros alfabéticamente), las personas suelen usar intuitivamente la ordenación por inserción para conjuntos pequeños. Para conjuntos más grandes, a menudo se agrupan primero, por ejemplo, por letra inicial, y la agrupación múltiple permite una ordenación práctica de conjuntos muy grandes. El espacio suele ser relativamente barato, por ejemplo, extendiendo los objetos en el suelo o en una gran superficie, pero las operaciones son costosas, sobre todo mover un objeto a gran distancia; la localidad de referencia es importante. La ordenación por fusión también es práctica para objetos físicos, especialmente porque se pueden usar dos manos, una para cada lista que se va a fusionar, mientras que otros algoritmos, como la ordenación por montículos o la ordenación rápida, no son adecuados para el uso humano. Otros algoritmos, como la ordenación por biblioteca , una variante de la ordenación por inserción que deja espacios, también son prácticos para el uso físico.

Tipos simples

Dos de los algoritmos de ordenación más sencillos son la ordenación por inserción y la ordenación por selección. Ambos son eficientes con conjuntos de datos pequeños debido a su baja sobrecarga, pero no con conjuntos de datos grandes. En la práctica, la ordenación por inserción suele ser más rápida que la ordenación por selección, debido a que requiere menos comparaciones y ofrece un buen rendimiento con datos casi ordenados, por lo que se prefiere. Sin embargo, la ordenación por selección utiliza menos operaciones de escritura, por lo que se emplea cuando el rendimiento de escritura es un factor limitante.

Ordenación por inserción

El ordenamiento por inserción es un algoritmo de ordenamiento simple que es relativamente eficiente para listas pequeñas y listas mayormente ordenadas, y se usa frecuentemente 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, de manera similar a como se guarda dinero en la cartera.^{[ 17 ]} En arreglos, la nueva lista y los elementos restantes pueden compartir el espacio del arreglo, pero la inserción es costosa, ya que requiere desplazar todos los elementos siguientes una posición. Shellsort es una variante del ordenamiento por inserción que es más eficiente para listas más grandes.

Ordenación por selección

El algoritmo de ordenación por selección es un algoritmo de ordenación por comparación in situ . Tiene una complejidad ^deO ( n² ), lo que lo hace ineficiente en listas grandes, y generalmente su rendimiento es inferior al del algoritmo de ordenación por inserción , que es similar . El algoritmo de ordenación por selección destaca por su simplicidad y, en ciertas situaciones, ofrece ventajas de rendimiento sobre algoritmos más complejos.

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. ^{[ 18 ]} Realiza como máximo n intercambios y, por lo tanto, es útil cuando el intercambio es muy costoso.

Tipos eficientes

Los algoritmos de ordenación generales prácticos casi siempre se basan en un algoritmo con una complejidad temporal promedio (y generalmente una complejidad en el peor de los casos) de O( n log n ), de los cuales los más comunes son heapsort, merge sort y quicksort. Cada uno tiene ventajas y desventajas, siendo la más significativa que una implementación simple de merge sort utiliza O( n ) espacio adicional, y una implementación simple de quicksort tiene una complejidad en el peor de los casos de O( n² ⁾ . Estos problemas pueden resolverse o mitigarse a costa de un algoritmo más complejo.

Si bien estos algoritmos son asintóticamente eficientes con datos aleatorios, para lograr una eficiencia práctica con datos reales se utilizan diversas modificaciones. En primer lugar, la sobrecarga de estos algoritmos se vuelve significativa con conjuntos de datos pequeños, por lo que a menudo se utiliza un algoritmo híbrido, que suele recurrir a la ordenación por inserción una vez que los datos son suficientemente pequeños. En segundo lugar, los algoritmos suelen tener un rendimiento deficiente con datos ya ordenados o casi ordenados; estos son comunes en los datos reales y pueden ordenarse en tiempo O( n ) mediante algoritmos apropiados. Finalmente, también pueden ser inestables , y la estabilidad suele ser una propiedad deseable en un algoritmo de ordenación. Por lo tanto, a menudo se emplean algoritmos más sofisticados, como Timsort (basado en la ordenación por fusión) o Introsort (basado en Quicksort, que recurre a Heapsort).

Ordenación por fusión

El algoritmo de ordenación por fusión aprovecha la facilidad de combinar listas ya ordenadas en una nueva lista ordenada. Comienza comparando cada par de elementos (es decir, 1 con 2, luego 3 con 4...) e intercambiándolos si el primero debe ir después del segundo. Luego combina cada una de las listas de dos resultantes en listas de cuatro, luego combina esas listas de cuatro, y así sucesivamente; hasta que finalmente dos listas se combinan en la lista ordenada final. ^{[ 19 ]} De los algoritmos descritos aquí, este es el primero que se adapta 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 arreglos, ya que solo requiere acceso secuencial, no acceso aleatorio. Al ordenar arreglos, tiene una complejidad espacial adicional de O( n ) e implica una gran cantidad de copias en implementaciones simples; sin embargo, las listas enlazadas se pueden ordenar por fusión con espacio adicional constante, por lo que es el algoritmo de elección para ordenar listas enlazadas.

El algoritmo de ordenación por fusión ha experimentado un aumento relativamente reciente en popularidad para implementaciones prácticas, debido a su uso en el sofisticado algoritmo Timsort , que se utiliza para la rutina de ordenación estándar en los lenguajes de programación Python ^{[ 20 ]} y Java (desde JDK7 ^{[ 21 ]} ). La propia ordenación por fusión es la rutina estándar en Perl [ ²²^]^, entre otros, y se ha utilizado en Java al menos desde el año 2000 en JDK1.3 [ ²³^]^.

Ordenación por montones

Heapsort es una versión mucho más eficiente de la ordenación por selección . También funciona determinando el elemento más grande (o más pequeño) de la lista, colocándolo al final (o al principio) de la lista, y luego continuando con el resto de la lista, pero realiza esta tarea de manera eficiente utilizando una estructura de datos llamada montón , un tipo especial de árbol binario . ^{[ 24 ]} 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 de manera que el elemento más grande restante se mueve a la raíz. Usando el montón, encontrar el siguiente elemento más grande toma un tiempo de O(log n ), en lugar de O( n ) para un escaneo lineal como en la ordenación por selección simple. Esto permite que Heapsort se ejecute en un tiempo de O( n log n ), y esta es también la complejidad en el peor de los casos.

Ordenación rápida

Quicksort es un algoritmo de divide y vencerás que se basa en una operación de partición : para particionar un arreglo, se selecciona un elemento llamado pivote . ^{[ 25 ]}^{[ 26 ]} Todos los elementos menores que el pivote se mueven antes de él y todos los elementos mayores se mueven después de él. Esto se puede hacer de manera eficiente en tiempo lineal y en el mismo lugar . Las sublistas menores y mayores se ordenan luego recursivamente. Esto produce una complejidad temporal promedio de O( n log n ), con una sobrecarga baja, por lo que es un algoritmo popular. Las implementaciones eficientes de quicksort (con partición en el mismo lugar) suelen ser ordenaciones inestables y algo complejas, pero se encuentran entre los algoritmos de ordenació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 ordenació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, lo cual es un caso común. El problema más complejo en quicksort es ^, por lo tanto, elegir un buen elemento pivote, ya que las elecciones consistentemente malas de pivotes pueden resultar en un rendimiento O( n² ) drásticamente más lento, pero una buena elección de pivotes produce un rendimiento O( n log n ), que es asintóticamente óptimo. Por ejemplo, si en cada paso se elige la mediana como pivote, entonces el algoritmo funciona en O( n log n ). Sin embargo, encontrar la mediana, como por ejemplo mediante el algoritmo de selección de medianas de medianas , es una operación O( n ) en listas no ordenadas y, por lo tanto, requiere una sobrecarga significativa con la ordenación. En la práctica, elegir un pivote aleatorio casi con certeza produce un rendimiento O( n log n ).

Si es importante garantizar un rendimiento O( n log n ), existe una modificación sencilla para lograrlo. La idea, debida a Musser, consiste en establecer un límite en la profundidad máxima de la recursión. ^{[ 27 ]} Si se supera ese límite, la ordenación continúa utilizando el algoritmo heapsort. Musser propuso que el límite debería ser $1+2\lfloor \log _{2}(n)\rfloor$ , lo cual es aproximadamente el doble de la profundidad de recursión máxima que se esperaría en promedio con una matriz ordenada aleatoriamente .

Shellsort

Shellsort fue inventado por Donald Shell en 1959. ^{[ 28 ]} Mejora el ordenamiento por inserción moviendo elementos fuera de orden más de una posición a la vez. El concepto detrás de Shellsort es que el ordenamiento por inserción se realiza en $O(kn)$ tiempo , donde k es la mayor distancia entre dos elementos fuera de lugar. Esto significa que, en general, se ejecutan en^O( n² ) , pero para datos que están mayormente ordenados, con solo unos pocos elementos fuera de lugar, se ejecutan más rápido. Por lo tanto, al ordenar primero los elementos alejados y reducir progresivamente el espacio entre los elementos a 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 usando la ordenación por inserción.

La complejidad temporal 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 ² ) hasta O ( n ^4/3 ) y Θ( n log ²n ). Esto, combinado con el hecho de que Shellsort es in situ , solo necesita una cantidad relativamente pequeña de código y no requiere el uso de la pila de llamadas , lo hace útil en situaciones donde la memoria es escasa, como en sistemas embebidos y núcleos de sistemas operativos .

Ordenación de burbuja y variantes

El algoritmo de ordenación de burbuja, y variantes como el de peine y el de cóctel , son algoritmos de ordenación sencillos pero muy ineficientes. Se ven con frecuencia en textos introductorios debido a su facilidad de análisis, pero rara vez se utilizan en la práctica.

Clasificación de burbujas

El algoritmo de ordenación de burbuja es un algoritmo de ordenación que recorre continuamente una lista, intercambiando elementos hasta que aparecen en el orden correcto.

El algoritmo de ordenación de burbuja es un algoritmo de ordenación simple. Comienza al inicio del conjunto de datos. Compara los dos primeros elementos y, si el primero es mayor que el segundo, los intercambia. Continúa haciendo esto para cada par de elementos adyacentes hasta el final del conjunto de datos. Luego comienza de nuevo con los dos primeros elementos, repitiendo hasta que no se hayan producido intercambios en la última pasada. ^{[ 29 ]} El tiempo promedio y el rendimiento en el peor de los casos de este algoritmo es O( n ² ), por lo que rara vez se utiliza para ordenar conjuntos de datos grandes y desordenados. El algoritmo de ordenación de burbuja se puede utilizar para ordenar una pequeña cantidad de elementos (donde su ineficiencia asintótica no es una penalización alta). El algoritmo de ordenación de burbuja también se puede utilizar 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 un número cualquiera de elementos están fuera de lugar por solo una posición (por ejemplo, 0123546789 y 1032547698), el intercambio del algoritmo de ordenación de burbuja los ordenará en la primera pasada, la segunda pasada encontrará todos los elementos en orden, por lo que la ordenación tomará solo 2 n veces.

Clasificación por peine

El ordenamiento de peine es un algoritmo de ordenamiento relativamente simple basado en el ordenamiento de burbuja y diseñado originalmente por Włodzimierz Dobosiewicz en 1980. ^{[ 30 ]} Posteriormente 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 un ordenamiento de burbuja estos ralentizan enormemente el ordenamiento. ( Los conejos , valores grandes alrededor del principio de la lista, no representan un problema en el ordenamiento de burbuja) Lo logra intercambiando inicialmente elementos que están a cierta distancia entre sí en el arreglo, en lugar de intercambiar solo elementos si son adyacentes entre sí, y luego reduciendo la distancia elegida hasta que funcione como un ordenamiento de burbuja normal. Por lo tanto, si Shellsort puede pensarse como una versión generalizada del ordenamiento de inserción que intercambia elementos espaciados a cierta distancia entre sí, el ordenamiento de peine puede pensarse como la misma generalización aplicada al ordenamiento de burbuja.

Clasificación de distribución

La ordenación por distribución se refiere a cualquier algoritmo de ordenación en el que los datos se distribuyen desde su entrada a múltiples estructuras intermedias, que luego se recopilan y se colocan en la salida. Por ejemplo, tanto la ordenación por cubetas como la ordenación rápida son algoritmos de ordenación basados en la distribución. Estos algoritmos pueden utilizarse en un solo procesador o ser algoritmos distribuidos , donde los subconjuntos individuales se ordenan por separado en diferentes procesadores y luego se combinan. Esto permite la ordenación externa de datos demasiado grandes para caber en la memoria de un solo ordenador.

Clasificación por conteo

El algoritmo de 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 requiere memoria O(| S |), donde n es la longitud de la entrada. Funciona creando un arreglo de enteros de tamaño | S | y utilizando el i -ésimo bin para contar las ocurrencias del i -ésimo elemento de S en la entrada. Cada entrada se cuenta incrementando el valor de su bin correspondiente. Posteriormente, se recorre el arreglo de conteo para ordenar todas las entradas. Este algoritmo de ordenación a menudo no se puede utilizar porque S debe ser razonablemente pequeño para que el algoritmo sea eficiente, pero es extremadamente rápido y demuestra un excelente comportamiento asintótico a medida que n aumenta. También se puede modificar para proporcionar un comportamiento estable.

Clasificación por cubos

El algoritmo de ordenación por cubetas es un algoritmo de ordenación de divide y vencerás que generaliza la ordenación por conteo dividiendo un arreglo en un número finito de cubetas. Cada cubeta se ordena individualmente, ya sea utilizando un algoritmo de ordenación diferente o aplicando recursivamente el algoritmo de ordenación por cubetas.

La ordenación por cubetas funciona mejor cuando los elementos del conjunto de datos están distribuidos uniformemente entre todas las cubetas.

Ordenación por radix

El algoritmo de ordenación por radix ordena los números procesando sus dígitos individualmente. Ordena n números de k dígitos cada uno en tiempo O( n · k ). Este algoritmo puede procesar los dígitos de cada número comenzando por el dígito menos significativo (LSD) o por el más significativo (MSD). El algoritmo LSD ordena primero la lista por el dígito menos significativo, conservando su orden relativo mediante una ordenación estable. Luego, ordena por el siguiente dígito, y así sucesivamente, desde el menos significativo hasta el más significativo, obteniendo una lista ordenada. Si bien el algoritmo LSD requiere el uso de una ordenación estable, el algoritmo MSD no lo requiere (a menos que se desee una ordenación estable). La ordenación MSD in situ no es estable. Es común que el algoritmo de ordenación por conteo se utilice internamente en el algoritmo de ordenación por radix. Un enfoque de ordenación híbrido , como el uso de la ordenación por inserción para grupos pequeños, mejora significativamente el rendimiento del algoritmo de ordenación por radix.

Tabla de tiempos de ejecución de algoritmos populares

En Algorithms and Data Structures, Niklaus Wirth ofrece una comparación del tiempo de ejecución de varios de los algoritmos más populares en la computadora Lilith . ^{[ 31 ]}

Patrones de uso de memoria y ordenación por índice

Cuando el tamaño del array que se va a ordenar se acerca o supera la memoria principal disponible, de modo que se debe utilizar espacio en disco o de intercambio (mucho más lento), el patrón de uso de memoria de un algoritmo de ordenación cobra importancia, y un algoritmo que podría haber sido bastante eficiente cuando el array cabía fácilmente en la RAM puede volverse impráctico. En este escenario, el número total de comparaciones se vuelve (relativamente) menos importante, y la cantidad de veces que se deben copiar o intercambiar secciones de memoria desde y hacia el disco puede dominar las características de rendimiento de un algoritmo. Por lo tanto, el número de pasadas y la localización de las comparaciones pueden ser más importantes que el número bruto de comparaciones, ya que las comparaciones de elementos cercanos entre sí se realizan a la velocidad del bus del sistema (o, con caché, incluso a la velocidad de la CPU ), lo que, en comparación con la velocidad del disco, es prácticamente instantáneo.

Por ejemplo, el popular algoritmo de ordenación rápida recursiva ofrece un rendimiento bastante aceptable con suficiente memoria RAM, pero debido a su naturaleza recursiva al copiar partes del array, resulta mucho menos práctico cuando este no cabe en la RAM, ya que puede provocar numerosas operaciones lentas de copia o movimiento desde y hacia el disco. En ese caso, otro algoritmo podría ser preferible, incluso si requiere un mayor número de comparaciones.

Una forma de solucionar este problema, que funciona bien cuando se ordenan registros complejos (como en una base de datos relacional ) mediante un campo clave relativamente pequeño, es crear un índice en la matriz y luego ordenar el índice, en lugar de la matriz completa. (Se puede generar una versión ordenada de toda la matriz en una sola pasada, leyendo desde el índice, pero a menudo incluso eso es innecesario, ya que el índice ordenado es suficiente). Debido a que el índice es mucho más pequeño que la matriz completa, puede caber fácilmente en la memoria donde la matriz completa no cabría, eliminando así el problema del intercambio de disco. Este procedimiento a veces se denomina "ordenación por etiquetas". ^{[ 32 ]}

Otra técnica para superar el problema del tamaño de la memoria es usar la ordenación externa ; por ejemplo, una forma es combinar dos algoritmos aprovechando las ventajas de cada uno para mejorar el rendimiento general. Por ejemplo, el array podría subdividirse en fragmentos de un tamaño que quepa en la RAM, el contenido de cada fragmento se ordena usando un algoritmo eficiente (como quicksort ) y los resultados se combinan usando una fusión de k vías similar a la que se usa en merge sort . Esto es más rápido que realizar merge sort o quicksort sobre toda la lista. ^{[ 33 ]}^{[ 34 ]}

También se pueden combinar técnicas. Para ordenar conjuntos de datos muy grandes que superan con creces la memoria del sistema, incluso el índice puede necesitar ser ordenado utilizando un algoritmo o una combinación de algoritmos diseñados para funcionar razonablemente bien con la memoria virtual , es decir, para reducir la cantidad de intercambio de memoria necesaria.

Algoritmos relacionados

Los problemas relacionados incluyen la ordenación aproximada (ordenar una secuencia con una precisión de un cierto grado respecto al orden correcto), la ordenación parcial (ordenar solo los k elementos más pequeños de una lista, o encontrar los k elementos más pequeños, pero sin orden específico) y la selección (calcular el k -ésimo elemento más pequeño). Estos problemas pueden resolverse de forma ineficiente mediante una ordenación total, pero existen algoritmos más eficientes, a menudo derivados de la generalización de un algoritmo de ordenación. El ejemplo más notable es quickselect , que está relacionado con quicksort . Por el contrario, algunos algoritmos de ordenación pueden derivarse mediante la aplicación repetida de un algoritmo de selección; quicksort y quickselect pueden considerarse como el mismo movimiento de pivote, diferenciándose únicamente en si se recurre en ambos lados (quicksort, divide y vencerás ) o en un solo lado (quickselect, reduce y conquista ).

Un algoritmo de barajado es, en cierto modo, lo opuesto a un algoritmo de ordenación . Estos son fundamentalmente diferentes porque requieren una fuente de números aleatorios. El barajado también puede implementarse mediante un algoritmo de ordenación, concretamente mediante una ordenación aleatoria: asignando un número aleatorio a cada elemento de la lista y luego ordenando en función de esos números aleatorios. Sin embargo, esto no se suele hacer en la práctica, y existe un algoritmo de barajado sencillo y eficiente muy conocido: el algoritmo de Fisher-Yates .

Los algoritmos de ordenación resultan ineficaces para encontrar un orden en muchas situaciones. Generalmente, cuando los elementos carecen de una función de comparación fiable (preferencias colectivas como los sistemas de votación ), las comparaciones son muy costosas ( deportes ) o cuando sería imposible comparar por pares todos los elementos según todos los criterios ( motores de búsqueda ). En estos casos, el problema se suele denominar clasificación y el objetivo es encontrar el "mejor" resultado para ciertos criterios según las probabilidades inferidas a partir de comparaciones o clasificaciones. Un ejemplo común es el ajedrez, donde los jugadores se clasifican con el sistema de puntuación Elo y las clasificaciones se determinan mediante un sistema de torneos en lugar de un algoritmo de ordenación.

Existen algoritmos de ordenación para un comparador "ruidoso" (potencialmente incorrecto) y algoritmos de ordenación para un par de comparadores "rápidos y sucios" (es decir, "ruidosos") y "limpios". Esto puede ser útil cuando la función de comparación completa es costosa. ^{[ 35 ]}

Véase también

Cotejo – Recopilación de información escrita en un orden estándar
Secuencia clasificada por K
Transformación de Schwartz : modismo de programación para ordenar eficientemente una lista mediante una clave calculada.
Algoritmo de búsqueda : cualquier algoritmo que resuelva el problema de búsqueda.
Ordenación cuántica : algoritmos de ordenación para ordenadores cuánticos

Referencias

↑ "Conozca a las 'damas de la nevera' que programaron el ENIAC" . Mental Floss . 13 de octubre de 2013. Archivado del original el 8 de octubre de 2018. Consultado el 16 de junio de 2016 .
↑ Lohr, Steve (17 de diciembre de 2001). "Frances E. Holberton, de 84 años, pionera en la programación informática" . NYTimes. Archivado del original el 16 de diciembre de 2014. Consultado el 16 de diciembre de 2014 .
↑ Demuth, Howard B. (1956). Clasificación electrónica de datos (tesis doctoral). Universidad de Stanford. ProQuest 301940891 .
^ Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L .; Stein, Clifford (2009), "8", Introducción a los algoritmos (3.ª ed.), Cambridge, MA: The MIT Press, p. 167, ISBN 978-0-262-03293-3
↑ 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 de la ACM sobre Teoría de la Computación . págs. 1–9 . doi : 10.1145/800061.808726 . ISBN 0-89791-099-0.
↑ Kim, PS; Kutzner, A. (2008). Fusión estable in situ basada en ratios . TAMC 2008. Teoría y aplicaciones de modelos de computación . LNCS . Vol. 4978. pp. 246–257 . CiteSeerX 10.1.1.330.2641 . doi : 10.1007/978-3-540-79228-4_22 . ISBN 978-3-540-79227-7.
↑ Sedgewick, Robert (1 de septiembre de 1998). Algoritmos en C: Fundamentos, Estructuras de datos, Ordenación, Búsqueda, Partes 1-4 (3.ª ed.). Pearson Education. ISBN 978-81-317-1291-7Consultado el 27 de noviembre de 2012 .
↑ Sedgewick, R. (1978). "Implementación de programas Quicksort". Comm. ACM . 21 (10): 847– 857. doi : 10.1145/359619.359631 . S2CID 10020756 .
↑ 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ág. 165, ISBN 0-262-03293-7
↑ Nilsson, Stefan (2000). "¿El algoritmo de ordenación más rápido?" . Dr. Dobb's . Archivado del original el 8 de junio de 2019 . Recuperado el 23 de noviembre de 2015 .
1 2 3 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.
1 2 Goodrich, Michael T. ; Tamassia, Roberto (2002). "4.5 Ordenación por cubetas y ordenación por radix". Diseño de algoritmos: fundamentos, análisis y ejemplos de Internet . John Wiley & Sons. págs. 241–243 . ISBN 978-0-471-38365-9.
↑ Gruber, H.; Holzer, M.; Ruepp, O. (2007), "Sorting the slow way: an analysis of perversely awful randomized sorting algorithms", 4th International Conference on Fun with Algorithms, Castiglioncello, Italia, 2007 (PDF) , Lecture Notes in Computer Science, vol. 4475, Springer-Verlag, pp. 183–197 , doi : 10.1007/978-3-540-72914-3_17 , ISBN 978-3-540-72913-6, archivado (PDF) del original el 29/09/2020 , recuperado el 27/06/2020.
1 2 Thorup, M. (febrero de 2002). "Ordenación aleatoria en tiempo O(n log log n) y espacio lineal utilizando suma, desplazamiento y operaciones booleanas a nivel de bits". Journal of Algorithms . 42 (2): 205– 230. doi : 10.1006/jagm.2002.1211 . S2CID 9700543 .
↑ Andersson, Arne; Hagerup, Torben; Nilsson, Stefan; Raman, Rajeev (1995). "¿Clasificación en tiempo lineal?". Actas del vigésimo séptimo simposio anual de la ACM sobre Teoría de la Computación . ACM. págs. 427–436 .
↑ Han, Yijie; Thorup, M. (2002). Ordenación de enteros en tiempo esperado O(n√(log log n)) y espacio lineal . 43.º Simposio Anual IEEE sobre Fundamentos de la Informática . pp. 135–144 . doi : 10.1109/SFCS.2002.1181890 . ISBN 0-7695-1822-2.
↑ Wirth, Niklaus (1986). Algoritmos y estructuras de datos . Upper Saddle River, NJ: Prentice-Hall. págs. 76–77 . ISBN 978-0130220059.
↑ Wirth 1986 , págs. 79–80
↑ Wirth 1986 , págs. 101–102
↑ "Descripción original de timsort por Tim Peters" . python.org . Archivado del original el 22 de enero de 2018. Consultado el 14 de abril de 2018 .
↑ "TimSort.java de OpenJDK" . java.net . Archivado del original el 14 de agosto de 2011. Consultado el 14 de abril de 2018 .
↑ "sort – perldoc.perl.org" . perldoc.perl.org . Archivado del original el 14 de abril de 2018 . Recuperado el 14 de abril de 2018 .
↑ Ordenación por fusión en Java 1.3 , dom. Archivado el 4 de marzo de 2009 en Wayback Machine.
↑ Wirth 1986 , págs. 87–89
↑ Wirth 1986 , pág. 93
^ Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L .; Stein, Clifford (2009), Introducción a los algoritmos (3.ª ed.), Cambridge, MA: The MIT Press, págs. 171-172 , ISBN 978-0262033848
↑ Musser, David R. (1997), "Algoritmos de ordenación y selección introspectivos", Software: Practice and Experience , 27 (8): 983– 993, doi : 10.1002/(SICI)1097-024X(199708)27:8 < 983::AID-SPE117 > 3.0.CO ; 2-#
↑ Shell, DL (1959). "Un procedimiento de clasificación de alta velocidad" (PDF) . Communications of the ACM . 2 (7): 30– 32. doi : 10.1145/368370.368387 . S2CID 28572656. Archivado del original (PDF) el 30 de agosto de 2017. Recuperado el 23 de marzo de 2020 .
↑ Wirth 1986 , págs. 81–82
↑ Brejová, B. (15 de septiembre de 2001). "Análisis de variantes de Shellsort". Inf. Process. Lett. 79 (5): 223– 227. doi : 10.1016/S0020-0190(00)00223-4 .
↑ Wirth 1986 , pág. 100.
↑ "Definición de ordenación de etiquetas de la enciclopedia de PC Magazine" . Pcmag.com . Archivado del original el 6 de octubre de 2012. Consultado el 14 de abril de 2018 .
↑ Donald Knuth , El arte de la programación informática , Volumen 3: Ordenación y búsqueda , Segunda edición. Addison-Wesley, 1998, ISBN 0-201-89685-0, Sección 5.4: Clasificación externa, págs. 248–379.
↑ Ellis Horowitz y Sartaj Sahni , Fundamentos de estructuras de datos , H. Freeman & Co., ISBN 0-7167-8042-9.
↑ Bai, Xingjian; Coester, Christian (2023). Ordenación con predicciones . NeurIPS. pág. 5.

Lecturas adicionales

Knuth, Donald E. (1998), Ordenación y búsqueda , El arte de la programación informática, vol. 3 (2.ª ed.), Boston: Addison-Wesley, ISBN 0-201-89685-0
Sedgewick, Robert (1980), "Clasificación eficiente por computadora: una introducción" , Computational Probability , Nueva York: Academic Press, pp. 101–130 , ISBN 0-12-394680-8

Enlaces externos

Animaciones de algoritmos de ordenación en Wayback Machine (archivado el 3 de marzo de 2015) .
Algoritmos de ordenación secuenciales y paralelos : explicaciones y análisis de numerosos algoritmos de ordenación.
Diccionario de algoritmos, estructuras de datos y problemas : diccionario de algoritmos, técnicas, funciones comunes y problemas.
Una visión ligeramente escéptica sobre los algoritmos de ordenación : analiza varios algoritmos clásicos y propone alternativas al algoritmo Quicksort .
15 algoritmos de ordenación en 6 minutos (Youtube) – Visualización y "audibilización" de 15 algoritmos de ordenación en 6 minutos.
Secuencia A036604 en la base de datos OEIS titulada "Ordenar números: número mínimo de comparaciones necesarias para ordenar n elementos" – Realizada por el algoritmo Ford–Johnson .
Algoritmos de ordenación utilizados en pinturas famosas (Youtube) – Visualización de algoritmos de ordenación en muchas pinturas famosas.
Comparación de algoritmos de ordenación : ejecuta una serie de pruebas de 9 de los principales algoritmos de ordenación utilizando Python timeit y Google Colab .

[refrigerator-1] "Conozca a las 'damas de la nevera' que programaron el ENIAC" . Mental Floss . 13 de octubre de 2013. Archivado del original el 8 de octubre de 2018. Consultado el 16 de junio de 2016 .

[NYTimes-2] Lohr, Steve (17 de diciembre de 2001). "Frances E. Holberton, de 84 años, pionera en la programación informática" . NYTimes. Archivado del original el 16 de diciembre de 2014. Consultado el 16 de diciembre de 2014 .

[3] Demuth, Howard B. (1956). Clasificación electrónica de datos (tesis doctoral). Universidad de 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] 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 de la ACM sobre Teoría de la Computación . págs. 1–9 . doi : 10.1145/800061.808726 . ISBN 0-89791-099-0.

[6] Kim, PS; Kutzner, A. (2008). Fusión estable in situ basada en ratios . TAMC 2008. Teoría y aplicaciones de modelos de computación . LNCS . Vol. 4978. pp. 246–257 . CiteSeerX 10.1.1.330.2641 . doi : 10.1007/978-3-540-79228-4_22 . ISBN 978-3-540-79227-7.

[7] Sedgewick, Robert (1 de septiembre de 1998). Algoritmos en C: Fundamentos, Estructuras de datos, Ordenación, Búsqueda, Partes 1-4 (3.ª ed.). Pearson Education. ISBN 978-81-317-1291-7Consultado el 27 de noviembre de 2012 .

[sedgewickQsortPaper-8] Sedgewick, R. (1978). "Implementación de programas Quicksort". Comm. ACM . 21 (10): 847– 857. doi : 10.1145/359619.359631 . S2CID 10020756 .

[9] 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ág. 165, ISBN 0-262-03293-7

[10] Nilsson, Stefan (2000). "¿El algoritmo de ordenación más rápido?" . Dr. Dobb's . Archivado del original el 8 de junio de 2019 . Recuperado el 23 de noviembre de 2015 .

[clrs-11] 1 2 3 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.

[gt-12] 1 2 Goodrich, Michael T. ; Tamassia, Roberto (2002). "4.5 Ordenación por cubetas y ordenación por radix". Diseño de algoritmos: fundamentos, análisis y ejemplos de Internet . John Wiley & Sons. págs. 241–243 . ISBN 978-0-471-38365-9.

[Fun07-13] Gruber, H.; Holzer, M.; Ruepp, O. (2007), "Sorting the slow way: an analysis of perversely awful randomized sorting algorithms", 4th International Conference on Fun with Algorithms, Castiglioncello, Italia, 2007 (PDF) , Lecture Notes in Computer Science, vol. 4475, Springer-Verlag, pp. 183–197 , doi : 10.1007/978-3-540-72914-3_17 , ISBN 978-3-540-72913-6, archivado (PDF) del original el 29/09/2020 , recuperado el 27/06/2020.

[:0-14] 1 2 Thorup, M. (febrero de 2002). "Ordenación aleatoria en tiempo O(n log log n) y espacio lineal utilizando suma, desplazamiento y operaciones booleanas a nivel de bits". Journal of Algorithms . 42 (2): 205– 230. doi : 10.1006/jagm.2002.1211 . S2CID 9700543 .

[15] Andersson, Arne; Hagerup, Torben; Nilsson, Stefan; Raman, Rajeev (1995). "¿Clasificación en tiempo lineal?". Actas del vigésimo séptimo simposio anual de la ACM sobre Teoría de la Computación . ACM. págs. 427–436 .

[16] Han, Yijie; Thorup, M. (2002). Ordenación de enteros en tiempo esperado O(n√(log log n)) y espacio lineal . 43.º Simposio Anual IEEE sobre Fundamentos de la Informática . pp. 135–144 . doi : 10.1109/SFCS.2002.1181890 . ISBN 0-7695-1822-2.

[17] Wirth, Niklaus (1986). Algoritmos y estructuras de datos . Upper Saddle River, NJ: Prentice-Hall. págs. 76–77 . ISBN 978-0130220059.

[18] Wirth 1986 , págs. 79–80

[19] Wirth 1986 , págs. 101–102

[20] "Descripción original de timsort por Tim Peters" . python.org . Archivado del original el 22 de enero de 2018. Consultado el 14 de abril de 2018 .

[21] "TimSort.java de OpenJDK" . java.net . Archivado del original el 14 de agosto de 2011. Consultado el 14 de abril de 2018 .

[22] "sort – perldoc.perl.org" . perldoc.perl.org . Archivado del original el 14 de abril de 2018 . Recuperado el 14 de abril de 2018 .

[mergesort_in_jdk13-23] Ordenación por fusión en Java 1.3 , dom. Archivado el 4 de marzo de 2009 en Wayback Machine.

[24] Wirth 1986 , págs. 87–89

[25] Wirth 1986 , pág. 93

[26] 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

[27] Musser, David R. (1997), "Algoritmos de ordenación y selección introspectivos", Software: Practice and Experience , 27 (8): 983– 993, doi : 10.1002/(SICI)1097-024X(199708)27:8 < 983::AID-SPE117 > 3.0.CO ; 2-#

[Shell-28] Shell, DL (1959). "Un procedimiento de clasificación de alta velocidad" (PDF) . Communications of the ACM . 2 (7): 30– 32. doi : 10.1145/368370.368387 . S2CID 28572656. Archivado del original (PDF) el 30 de agosto de 2017. Recuperado el 23 de marzo de 2020 .

[29] Wirth 1986 , págs. 81–82

[BB-30] Brejová, B. (15 de septiembre de 2001). "Análisis de variantes de Shellsort". Inf. Process. Lett. 79 (5): 223– 227. doi : 10.1016/S0020-0190(00)00223-4 .

[FOOTNOTEWirth1986100-31] Wirth 1986 , pág. 100.

[32] "Definición de ordenación de etiquetas de la enciclopedia de PC Magazine" . Pcmag.com . Archivado del original el 6 de octubre de 2012. Consultado el 14 de abril de 2018 .

[33] Donald Knuth , El arte de la programación informática , Volumen 3: Ordenació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.

[34] Ellis Horowitz y Sartaj Sahni , Fundamentos de estructuras de datos , H. Freeman & Co., ISBN 0-7167-8042-9.

[35] Bai, Xingjian; Coester, Christian (2023). Ordenación con predicciones . NeurIPS. pág. 5.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 9 ]

[ 10 ]

[ 15 ]

[ 16 ]

[ 17 ]

[ 18 ]

[ 19 ]

[ 20 ]

[ 21 ]

22

,

[ 24 ]

[ 25 ]

[ 26 ]

[ 27 ]

[ 28 ]

[ 29 ]

[ 30 ]

[ 31 ]

[ 32 ]

[ 33 ]

[ 34 ]

[ 35 ]