Shellsort

Shellsort , también conocido como Shell sort o método de Shell , es un algoritmo de ordenación por comparación in situ . Puede entenderse como una generalización de la ordenación por intercambio ( ordenación de burbuja ) o por inserción ( ordenación por inserción ). ^{[ 3 ]} El método comienza ordenando pares de elementos muy alejados entre sí, y luego reduce progresivamente la distancia 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ápidamente que un simple intercambio de vecinos más cercanos. El tiempo de ejecución de Shellsort depende en gran medida de la secuencia de separación que utiliza. Para muchas variantes prácticas, determinar su complejidad temporal sigue siendo un problema abierto .

El algoritmo fue publicado por primera vez por Donald Shell en 1959 y no tiene nada que ver con conchas. ^{[ 4 ] [ 5 ]}

Shellsort es una optimización del ordenamiento por inserción que permite el intercambio de elementos muy distantes. La idea es organizar la lista de elementos de manera que, comenzando en cualquier posición, al tomar cada h -ésimo elemento se obtenga una lista ordenada. Dicha lista se denomina h -ordenada. También puede considerarse como h listas intercaladas, cada una ordenada individualmente. ^{[ 6 ]} Comenzar con valores grandes de h permite que los elementos se muevan grandes distancias en la lista original, reduciendo rápidamente grandes cantidades de desorden y dejando menos trabajo para los pasos de h -ordenamiento más pequeños. ^{[ 7 ]} Si la lista se ordena luego k-ordenada para algún entero k más pequeño , entonces la lista permanece h- ordenada. Un ordenamiento final con h  =  1 asegura que la lista esté completamente ordenada al final, ^{[ 6 ]} pero una secuencia decreciente de valores de h elegida con criterio deja muy poco trabajo para esta pasada final.

En términos sencillos, esto significa que si tenemos un array 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 el array en cuatro secciones (que comienzan 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 puede ser cualquiera, pero el último espacio siempre es 1 para finalizar la ordenación (finalizando efectivamente con una ordenación por inserción ordinaria).

A continuación se muestra un ejemplo de ejecución de Shellsort con huecos de 5, 3 y 1.

La primera pasada, 5-sorting, realiza una ordenación por inserción en cinco submatrices separadas ( a ₁ , a ₆ , a ₁₁ ), ( a ₂ , a ₇ , a ₁₂ ), ( a ₃ , a ₈ ), ( a ₄ , a ₉ ), ( a ₅ , a ₁₀ ). Por ejemplo, cambia la submatriz ( a ₁ , a ₆ , a ₁₁ ) de (62, 17, 25) a (17, 25, 62). La siguiente pasada, 3-sorting, realiza una ordenación por inserción en las tres submatrices ( a ₁ , a ₄ , a ₇ , a ₁₀ ), ( a ₂ , a ₅ , a ₈ , a ₁₁ ), ( a ₃ , a ₆ , a ₉ , a ₁₂ ). La última pasada, la ordenación 1, es una ordenación por inserción ordinaria de todo el array ( a ₁ ,..., a ₁₂ ).

Como ilustra el ejemplo, los subconjuntos sobre los que opera Shellsort son inicialmente cortos; posteriormente se vuelven más largos, pero casi ordenados. En ambos casos, el algoritmo de ordenación por inserción funciona de manera eficiente.

A diferencia del algoritmo de ordenación por inserción , Shellsort no es un algoritmo de ordenación estable, ya que las inserciones con huecos desplazan elementos iguales unos sobre otros, perdiendo así su orden original. Es un algoritmo de ordenación adaptativo, puesto que se ejecuta más rápido cuando la entrada está parcialmente ordenada.

Este es un ejemplo en C# que utiliza la secuencia de huecos de Marcin Ciura, con una ordenación por inserción interna.

usando System.Collections.Generic ;// Ordena un array a[0...n-1]. List < int > gaps = [ 701 , 301 , 132 , 57 , 23 , 10 , 4 , 1 ]; // Secuencia de huecos de Ciura// Comienza con el hueco más grande y ve bajando hasta un hueco de 1 // similar a la ordenación por inserción, pero en lugar de 1, se usa hueco en cada paso foreach ( int hueco in huecos ) { // Realiza una ordenación por inserción con hueco para cada elemento en huecos // Cada bucle deja a[0..hueco-1] en orden con hueco for ( int i = hueco ; i < n ; ++ i ) { // guarda a[i] en temp y crea un hueco en la posición i int temp = a [ i ]; // desplaza los elementos ordenados con hueco anteriormente hasta que se encuentre la ubicación correcta para a[i] for ( int j = i ; ( j >= hueco ) && ( a [ j - hueco ] > temp ); j ​​-= hueco ) { a [ j ] = a [ j - hueco ]; } // coloca temp (el a[i] original) en su ubicación correcta a [ j ] = temp ; } }

La cuestión de decidir qué secuencia de huecos utilizar es compleja. Cualquier secuencia de huecos que contenga 1 produce una ordenación correcta (ya que esto convierte la pasada final en una ordenación por inserción ordinaria); sin embargo, las propiedades de las versiones de Shellsort obtenidas de esta manera pueden ser muy diferentes. Un número insuficiente de huecos ralentiza las pasadas, y un número excesivo genera una sobrecarga.

La tabla que aparece a continuación compara la mayoría de las secuencias de huecos propuestas y publicadas hasta la fecha. Algunas de ellas tienen elementos decrecientes que dependen del tamaño del arreglo ordenado ( N ). Otras son secuencias infinitas crecientes, cuyos elementos menores que N deben utilizarse en orden inverso.

Cuando la representación binaria de N contiene muchos ceros consecutivos, Shellsort, utilizando la secuencia de huecos original de Shell ^, realiza Θ( N² ) comparaciones en el peor de los casos. Por ejemplo, esto ocurre cuando N es una potencia de dos y los elementos mayores y menores que la mediana ocupan posiciones impares y pares, respectivamente, ya que solo se comparan en la última pasada.

La implementación de Shellsort (GBY91) de Gonnet y Baeza-Yates también utiliza huecos que comienzan con N y se desempeña mejor que muchas de las otras secuencias en promedio ^{[ 13 ]} , pero también es propensa a un peor caso Θ( N ² ): Sea X un hueco en la secuencia. La razón común de los huecos de GBY91 de 2.2 permite que al menos dos enteros consecutivos Y e Y+1 sean iguales a X por división entera por 2.2. Elija Y o Y+1, el que sea par, para repetir el proceso, y se obtiene una cadena infinitamente larga de huecos pares > X por inducción. Con X = 1, se generan infinitas opciones para N donde todos los huecos de GBY91 > 1 son pares y por lo tanto son Θ( N ² ) en la misma entrada del peor caso antes mencionado para los huecos originales de Shell.

Aunque tiene una complejidad mayor que la O ( N  log N ) que es óptima para las ordenaciones por comparación, la versión de Pratt se presta a la ordenación de redes y tiene la misma complejidad de puerta asintótica que el clasificador bitónico de Batcher . 

Gonnet y Baeza-Yates observaron que Shellsort realiza la menor cantidad de comparaciones en promedio cuando las razones de los huecos sucesivos son aproximadamente iguales a 2.2. ^{[ 13 ]} Por eso su secuencia con razón 2.2 y la secuencia de Tokuda con razón 2.25 resultan eficientes. Sin embargo, se desconoce la razón de esto. Sedgewick recomienda usar huecos que tengan divisores comunes máximos bajos o que sean coprimos por pares . ^{[ 18 ]} Usar huecos que sean números impares parece ayudar: se han visto aceleraciones de alrededor del 25% en la práctica en comparación con el código original de Shell. Usar huecos que no sean múltiplos de 2, 3 o 5 parece reducir aún más los tiempos de ejecución: aceleraciones de alrededor del 35% en comparación con el original de Shell parecen posibles. Usar huecos que sean solo números primos (que terminan en 1) parece producir aceleraciones de alrededor del 40% en comparación con el código original.

Con respecto al número promedio de comparaciones, la secuencia de Ciura ^{[ 15 ]} tiene el mejor rendimiento conocido; no se determinaron brechas mayores a 701, pero la secuencia se puede extender aún más según la fórmula recursiva.${\displaystyle h_{k}=\lfloor 2.25h_{k-1}\rfloor }$.

La secuencia de Tokuda, definida por la fórmula simple${\displaystyle h_{k}=\lceil h'_{k}\rceil }$, dónde${\displaystyle h'_{k}=2.25h'_{k-1}+1}$,${\displaystyle h'_{1}=1}$, puede recomendarse para aplicaciones prácticas.

Si el tamaño máximo de entrada es pequeño, como puede ocurrir si Shellsort se utiliza en submatrices pequeñas mediante otro algoritmo de ordenación recursiva como quicksort o merge sort , entonces es posible tabular una secuencia óptima para cada tamaño de entrada. ^{[ 19 ] [ 20 ]} Para N = 128 y N = 1000, Ciura encontró empíricamente que (1, 4, 9, 24, 85) y (1, 4, 10, 23, 57, 156, 409, 995) realizaron el menor número de comparaciones en promedio, respectivamente. ^{[ 15 ]}

Se cumple la siguiente propiedad: después de ordenar h ₂ de cualquier arreglo ordenado h ₁ , el arreglo permanece ordenado h _1. ^{[ 21 ]} Todo arreglo ordenado h ₁ y ordenado h ₂ también está ordenado ( a ₁ h ₁ + a ₂ h ₂ ), para cualesquiera enteros no negativos a ₁ y a ₂ . La complejidad del peor caso de Shellsort está, por lo tanto, relacionada con el problema de Frobenius : para enteros dados h ₁ ,..., h _n con mcd = 1, el número de Frobenius g ( h ₁ ,..., h _n ) es el mayor entero que no puede representarse como a ₁ h ₁ + ... + a _n h _n con entero no negativo a ₁ ,..., 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 probados se muestran en la tabla anterior.

Mark Allen Weiss demostró que Shellsort se ejecuta en tiempo O ( N log N ) cuando el array 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 brechas práctica. Para brechas que son potencias de dos, Espelid calculó este promedio como${\displaystyle 0.5349N{\sqrt {N}}-0.4387N-0.097{\sqrt {N}}+O(1)}$. ^{[ 24 ]} Knuth determinó que la complejidad promedio de ordenar una matriz de N elementos con dos huecos ( h , 1) es${\displaystyle {\frac {2N^{2}}{h}}+{\sqrt {\pi N^{3}h}}}$. ^{[ 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 halló 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 realizado durante un Shellsort con tres huecos ( ch , cg , 1), donde h y g son coprimos, es${\displaystyle {\frac {N^{2}}{4ch}}+O(N)}$en el primer pase,${\displaystyle {\frac {1}{8g}}{\sqrt {\frac {\pi }{ch}}}(h-1)N^{3/2}+O(hN)}$en el segundo pase y${\displaystyle \psi (h,g)N+{\frac {1}{8}}{\sqrt {\frac {\pi }{c}}}(c-1)N^{3/2}+O\left((c-1)gh^{1/2}N\right)+O\left(c^{2}g^{3}h^{2}\right)}$en el tercer paso. ψ ( h , g ) en la última fórmula es una función complicada asintóticamente igual a${\displaystyle {\sqrt {\frac {\pi h}{128}}}g+O\left(g^{-1/2}h^{1/2}\right)+O\left(gh^{-1/2}\right)}$. En particular, cuando h = Θ( N ^7/15 ) y g = Θ( N ^1/5 ), el tiempo promedio de clasificación es O ( N ^23/15 ).

Basándose en experimentos, se conjetura que Shellsort con la secuencia de huecos 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 presentadas anteriormente para otras secuencias fallan cuando los arreglos ordenados contienen millones de elementos.      

El gráfico a continuación muestra el número promedio de comparaciones de elementos utilizadas por varias secuencias de huecos, dividido por el límite inferior teórico , es decir, log ₂ N !. La secuencia de Ciuria 1, 4, 10, 23, 57, 132, 301, 701 (etiquetada como Ci01) se ha extendido según la fórmula${\displaystyle h_{k}=\lfloor 2.25h_{k-1}\rfloor }$.

Aplicando la teoría de la complejidad de Kolmogorov , Jiang, Li y Vitányi ^{[ 27 ]} demostraron la siguiente cota inferior para el orden del número promedio de operaciones/tiempo de ejecución en un Shellsort _de p pasadas: Ω( pN 1 ^{+1/ p} ) cuando p  ≤  log₂N y Ω( pN ) cuando p > log₂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 del arreglo. Sin embargo, se desconoce si Shellsort puede alcanzar este orden asintótico de complejidad en el caso promedio, que es óptimo para los algoritmos de ordenación por comparación. La cota inferior fue mejorada por Vitányi ^{[ 28 ]} para cada número de pasadas.  ${\displaystyle p}$a ${\displaystyle \Omega (N\sum _{k=1}^{p}h_{k-1}/h_{k})}$ dónde${\displaystyle h_{0}=N}$. Este resultado implica, por ejemplo, la cota inferior de Jiang-Li-Vitányi para todos${\displaystyle p}$-pasa secuencias de incremento y mejora ese límite inferior para secuencias de incremento particulares. De hecho, todos los límites (inferiores y superiores) actualmente conocidos para el caso promedio coinciden precisamente 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${\displaystyle \Theta (N^{23/15})}$comparaciones/inversiones/tiempo de ejecución. La fórmula nos permite buscar secuencias de incrementos que produzcan límites inferiores desconocidos; por ejemplo, una secuencia de incrementos para cuatro pasadas que tenga un límite inferior mayor que ${\displaystyle \Omega (pn^{1+1/p})=\Omega (n^{5/4})}$para la secuencia de incremento ${\displaystyle h_{1}=n^{11/16},}$${\displaystyle h_{2}=n^{7/16},}$${\displaystyle h_{3}=n^{3/16},}$${\displaystyle h_{4}=1}$El límite inferior se convierte en ${\displaystyle T=\Omega (n\cdot (n^{1-11/16}+n^{11/16-7/16}+n^{7/16-3/16}+n^{3/16})=\Omega (n^{1+5/16})=\Omega (n^{21/16}).}$

La complejidad en el peor de los casos de cualquier versión de Shellsort es de orden superior: Plaxton, Poonen y Suel demostraron que crece al menos tan rápidamente como${\displaystyle \Omega \left(N\left({\log N \over \log \log N}\right)^{2}\right)}$. ^{[ 29 ] [ 30 ]} Robert Cypher demostró una cota inferior más fuerte:${\displaystyle \Omega \left(N{{(\log N)^{2}} \over {\log \log N}}\right)}$cuando${\displaystyle h_{s+1}>h_{s}}$a pesar de${\displaystyle s}$. ^{[ 31 ]}

Shellsort realiza más operaciones y tiene una tasa de fallos de caché mayor que quicksort . Sin embargo, dado que se puede implementar con poco código y no utiliza la pila de llamadas , algunas implementaciones de la función qsort en la biblioteca estándar de C destinadas a sistemas embebidos 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 subalgoritmo de ordenación introspectiva para ordenar submatrices cortas y evitar una ralentización cuando la profundidad de recursión supera un límite determinado. Este principio se emplea, por ejemplo, en el compresor bzip2 . ^{[ 34 ]}

• Clasificación por peine

• Knuth, Donald E. (1997). «El método de Shell». El arte de la programación informática. Volumen 3: Ordenación y búsqueda (2.ª  ed.). Reading, Massachusetts: Addison-Wesley. pp. 83–95 . ISBN  978-0-201-89685-5.
• Análisis del algoritmo Shellsort y algoritmos relacionados , Robert Sedgewick, Cuarto Simposio Europeo sobre Algoritmos, Barcelona, ​​septiembre de 1996.

• Algoritmos de ordenación animados: Shell Sort en Wayback Machine (archivado el 10 de marzo de 2015) – demostración gráfica
• Shellsort con huecos 5, 3, 1 como una danza folclórica húngara