Shellsort , también conocido como ordenamiento de Shell o método de Shell , es un ordenamiento por comparación en el lugar . Puede considerarse como una generalización del ordenamiento por intercambio ( ordenamiento de burbuja ) o del ordenamiento por inserción ( ordenamiento por inserción ). [3] El método comienza ordenando pares de elementos muy alejados entre sí, para luego reducir progresivamente la brecha entre los elementos que se van a comparar. Al comenzar con elementos alejados, puede mover algunos elementos fuera de lugar a la posición más rápido que un simple intercambio de vecino más cercano. Donald Shell publicó la primera versión de este ordenamiento en 1959. [4] [5] El tiempo de ejecución de Shellsort depende en gran medida de la secuencia de brechas que utiliza. Para muchas variantes prácticas, determinar su complejidad temporal sigue siendo un problema abierto .
Shellsort es una optimización de la ordenación por inserción que permite el intercambio de elementos que están muy separados. La idea es organizar la lista de elementos de modo que, comenzando en cualquier lugar, tomando cada elemento h th produzca una lista ordenada. Se dice que una lista de este tipo está h -ordenada. También se puede pensar en ella como h listas intercaladas, cada una ordenada individualmente. [6] Comenzar con valores grandes de h permite que los elementos se muevan largas distancias en la lista original, reduciendo grandes cantidades de desorden rápidamente y dejando menos trabajo para que lo hagan los pasos de h -ordenación más pequeños. [7] Si luego la lista se ordena k para algún entero más pequeño k , entonces la lista permanece h -ordenada. Una ordenación final con h = 1 asegura que la lista esté completamente ordenada al final, [6] pero una secuencia decreciente de valores h elegida juiciosamente deja muy poco trabajo para que lo haga este paso final.
En términos simplistas, esto significa que si tenemos una matriz de 1024 números, nuestro primer espacio ( h ) podría ser 512. Luego recorremos la lista comparando cada elemento de la primera mitad con el elemento de la segunda mitad. Nuestro segundo espacio ( k ) es 256, lo que divide la matriz en cuatro secciones (comenzando en 0, 256, 512, 768), y nos aseguramos de que los primeros elementos de cada sección estén ordenados entre sí, luego el segundo elemento de cada sección, y así sucesivamente. En la práctica, la secuencia de espacios podría ser cualquier cosa, pero el último espacio siempre es 1 para finalizar la ordenación (terminando efectivamente con una ordenación por inserción ordinaria).
A continuación se muestra un ejemplo de ejecución de Shellsort con los espacios 5, 3 y 1.
El primer paso, 5-sorting, realiza un ordenamiento por inserción en cinco submatrices independientes ( a 1 , a 6 , a 11 ), ( a 2 , a 7 , a 12 ), ( a 3 , a 8 ), ( a 4 , a 9 ), ( a 5 , a 10 ). Por ejemplo, cambia la submatriz ( a 1 , a 6 , a 11 ) de (62, 17, 25) a (17, 25, 62). El siguiente paso, 3-sorting, realiza un ordenamiento por inserción en las tres submatrices ( a 1 , a 4 , a 7 , a 10 ), ( a 2 , a 5 , a 8 , a 11 ), ( a 3 , a 6 , a 9 , a 12 ). El último paso, 1-sorting, es una ordenación por inserción ordinaria de toda la matriz ( un 1 ,..., un 12 ).
Como ilustra el ejemplo, los subconjuntos sobre los que opera Shellsort son inicialmente cortos; luego son más largos pero casi ordenados. En ambos casos, la ordenación por inserción funciona de manera eficiente.
A diferencia del ordenamiento por inserción , Shellsort no es un ordenamiento estable , ya que las inserciones con espacios en blanco transportan elementos iguales uno tras otro y, por lo tanto, pierden su orden original. Es un algoritmo de ordenamiento adaptativo , ya que se ejecuta más rápido cuando la entrada está parcialmente ordenada.
Utilizando la secuencia gap de Marcin Ciura, con una ordenación por inserción interna.
# Ordena una matriz a[0...n-1]. gaps = [ 701 , 301 , 132 , 57 , 23 , 10 , 4 , 1 ] # Secuencia de gaps de Ciura # Comience con el espacio más grande y trabaje hasta llegar a un espacio de 1 # similar al ordenamiento por inserción pero en lugar de 1, se usa un espacio en cada paso foreach ( gap in gaps ) { # Realice un ordenamiento por inserción con espacio para cada elemento en los espacios # Cada bucle deja a[0..gap-1] en orden con espacio for ( i = gap ; i < n ; i += 1 ) { # Guarde a[i] en temp y haga un agujero en la posición i temp = a [ i ] # Desplace los elementos anteriores ordenados con espacio hasta que se encuentre la ubicación correcta para a[i] for ( j = i ; ( j >= gap ) && ( a [ j - gap ] > temp ); j -= gap ) { a [ j ] = a [ j - gap ] } # Coloque temp (el a[i] original) en su ubicación correcta a [ j ] = temp } }
La cuestión de decidir qué secuencia de espacios utilizar es difícil. Toda secuencia de espacios que contenga 1 produce una ordenación correcta (ya que esto hace que el paso final sea una ordenación por inserción normal); sin embargo, las propiedades de las versiones de Shellsort así obtenidas pueden ser muy diferentes. Muy pocos espacios ralentizan los pasos y demasiados generan una sobrecarga.
La siguiente tabla compara la mayoría de las secuencias gap propuestas publicadas hasta el momento. Algunas de ellas tienen elementos decrecientes que dependen del tamaño de la matriz ordenada ( N ). Otras son secuencias infinitas crecientes, cuyos elementos menores a N deben usarse en orden inverso.
Cuando la representación binaria de N contiene muchos ceros consecutivos, Shellsort, que utiliza la secuencia de espacios en blanco original de Shell, realiza comparaciones Θ( N 2 ) en el peor de los casos. Por ejemplo, este caso se da para N igual a una potencia de dos cuando los elementos mayores y menores que la mediana ocupan posiciones pares e impares respectivamente, ya que se comparan solo en la última pasada.
Aunque tiene una complejidad mayor que la de O ( N log N ), que es óptima para los ordenamientos por comparación, la versión de Pratt se presta a redes de ordenamiento y tiene la misma complejidad de compuerta asintótica que el ordenamiento bitónico de Batcher .
Gonnet y Baeza-Yates observaron que Shellsort hace menos comparaciones en promedio cuando las razones de los huecos sucesivos son aproximadamente iguales a 2,2. [13] Es por esto que su secuencia con razón 2,2 y la secuencia de Tokuda con razón 2,25 resultan eficientes. Sin embargo, no se sabe por qué es así. Sedgewick recomienda usar huecos que tengan mínimos divisores comunes o que sean coprimos por pares . [18] [ verificación fallida ] Los huecos que son números impares parecen funcionar bien en la práctica: se han observado reducciones del 25% al evitar huecos de números pares. Los huecos que evitan múltiplos de 3 y 5 parecen producir pequeños beneficios de < 10%. [ investigación original? ]
Respecto al número promedio de comparaciones, la secuencia de Ciura [15] tiene el mejor desempeño conocido; no se determinaron brechas mayores a 701 pero la secuencia se puede extender aún más de acuerdo con la fórmula recursiva .
La secuencia de Tokuda, definida por la fórmula simple , donde , , puede recomendarse para aplicaciones prácticas.
Si el tamaño máximo de entrada es pequeño, como puede ocurrir si se utiliza Shellsort en submatrices pequeñas mediante otro algoritmo de ordenamiento recursivo como quicksort o merge sort , entonces es posible tabular una secuencia óptima para cada tamaño de entrada. [19] [20]
La siguiente propiedad se cumple: después de la h 2 -ordenación de cualquier matriz h 1 -ordenada, la matriz permanece h 1 -ordenada. [21] Toda matriz h 1 -ordenada y h 2 -ordenada también está ( a 1 h 1 + a 2 h 2 )-ordenada, para cualesquiera enteros no negativos a 1 y a 2 . Por lo tanto, la complejidad del peor caso de Shellsort está relacionada con el problema de Frobenius : para los enteros dados h 1 ,..., h n con mcd = 1, el número de Frobenius g ( h 1 ,..., h n ) es el mayor entero que no se puede representar como a 1 h 1 + ... + a n h n con el entero no negativo a 1 ,..., a n . Usando fórmulas conocidas para los números de Frobenius, podemos determinar la complejidad del peor caso de Shellsort para varias clases de secuencias de huecos. [22] Los resultados comprobados se muestran en la tabla anterior.
Mark Allen Weiss demostró que Shellsort se ejecuta en tiempo O ( N log N ) cuando la matriz de entrada está en orden inverso. [23]
Con respecto al número promedio de operaciones, ninguno de los resultados probados se refiere a una secuencia de huecos práctica. Para huecos que son potencias de dos, Espelid calculó este promedio como . [24] Knuth determinó que la complejidad promedio de ordenar una matriz de N elementos con dos huecos ( h , 1) es . [3] De ello se deduce que un Shellsort de dos pasadas con h = Θ( N 1/3 ) realiza en promedio O ( N 5/3 ) comparaciones/inversiones/tiempo de ejecución. Yao encontró la complejidad promedio de un Shellsort de tres pasadas. [25] Su resultado fue refinado por Janson y Knuth: [26] el número promedio de comparaciones/inversiones/tiempo de ejecución realizadas durante un Shellsort con tres huecos ( ch , cg , 1), donde h y g son coprimos, es en la primera pasada, en la segunda pasada y en la tercera pasada. ψ ( h , g ) en la última fórmula es una función complicada asintóticamente igual a . En particular, cuando h = Θ( N 7/15 ) y g = Θ( N 1/5 ), el tiempo promedio de clasificación es O ( N 23/15 ).
Con base en experimentos, se conjetura que Shellsort con la secuencia gap de Hibbard se ejecuta en un tiempo promedio de O ( N 5/4 ), [3] y que la secuencia de Gonnet y Baeza-Yates requiere en promedio 0,41 N ln N (ln ln N + 1/6) movimientos de elementos. [13] Las aproximaciones del número promedio de operaciones propuestas anteriormente para otras secuencias fallan cuando las matrices ordenadas contienen millones de elementos.
El gráfico siguiente muestra el número promedio de comparaciones de elementos utilizadas por varias secuencias gap, dividido por el límite inferior teórico , es decir, log 2 N !. La secuencia de Ciuria 1, 4, 10, 23, 57, 132, 301, 701 (etiquetada Ci01) se ha extendido de acuerdo con la fórmula .
Aplicando la teoría de la complejidad de Kolmogorov , Jiang, Li y Vitányi [27] demostraron el siguiente límite inferior para el orden del número promedio de operaciones/tiempo de ejecución en un Shellsort de p -pasos: Ω( pN 1+1/ p ) cuando p ≤ log 2 N y Ω( pN ) cuando p > log 2 N . Por lo tanto, Shellsort tiene perspectivas de ejecutarse en un tiempo promedio que crece asintóticamente como N log N solo cuando se utilizan secuencias de huecos cuyo número de huecos crece en proporción al logaritmo del tamaño de la matriz. Sin embargo, se desconoce si Shellsort puede alcanzar este orden asintótico de complejidad de caso promedio, que es óptimo para ordenamientos de comparación. El límite inferior fue mejorado por Vitányi [28] para cada número de pases hasta donde . Este resultado implica, por ejemplo, el límite inferior de Jiang-Li-Vitányi para todas las secuencias de incremento de -pasos y mejora ese límite inferior para secuencias de incremento particulares. De hecho, todos los límites (inferiores y superiores) conocidos actualmente para el caso promedio coinciden exactamente con este límite inferior. Por ejemplo, esto da el nuevo resultado de que el límite superior de Janson-Knuth coincide con el límite inferior resultante para la secuencia de incremento utilizada, lo que demuestra que Shellsort de tres pasadas para esta secuencia de incremento utiliza comparaciones/inversiones/tiempo de ejecución. La fórmula nos permite buscar secuencias de incremento que produzcan límites inferiores que son desconocidos; por ejemplo, una secuencia de incremento para cuatro pasadas que tenga un límite inferior mayor que para la secuencia de incremento . El límite inferior se convierte en
La complejidad del peor caso de cualquier versión de Shellsort es de orden superior: Plaxton, Poonen y Suel demostraron que crece al menos tan rápidamente como . [29] [30] Robert Cypher demostró un límite inferior más fuerte: cuando para todos . [31]
Shellsort realiza más operaciones y tiene una mayor tasa de errores de caché que quicksort . Sin embargo, dado que se puede implementar utilizando poco código y no utiliza la pila de llamadas , algunas implementaciones de la función qsort en la biblioteca estándar de C dirigidas a sistemas integrados la utilizan en lugar de quicksort. Shellsort se utiliza, por ejemplo, en la biblioteca uClibc . [32] Por razones similares, en el pasado, Shellsort se utilizó en el kernel de Linux . [33]
Shellsort también puede servir como un subalgoritmo de ordenación introspectiva , para ordenar submatrices cortas y evitar una ralentización cuando la profundidad de recursión excede un límite determinado. Este principio se emplea, por ejemplo, en el compresor bzip2 . [34]
Experimentos exhaustivos indican que la secuencia definida por
α
= 0,45454 < 5/11tiene
un rendimiento significativamente mejor que otras secuencias. La forma más sencilla de calcular
⌊
0,45454
n
⌋
es mediante
aritmética de números enteros.
(5 * n — 1)/11
{{cite book}}
: CS1 maint: location missing publisher (link)