Shellsort

Algoritmo de clasificación que utiliza múltiples intervalos de comparación

Shellsort

Shellsort con huecos 23, 10, 4, 1 en acción
Clase	Algoritmo de clasificación
Estructura de datos	Formación
Rendimiento en el peor de los casos	O ( n 2 ) (secuencia de espacios del peor caso más conocido) O ( n log 2 n ) (secuencia de espacios del peor caso más conocida) [1]
Rendimiento en el mejor de los casos	O ( n log n ) (la mayoría de las secuencias de huecos) O ( n log 2 n ) (la secuencia de huecos del peor caso más conocida) [2]
Rendimiento medio	depende de la secuencia de espacios
Complejidad espacial en el peor de los casos	О ( n ) total, O (1) auxiliar

Intercambiar pares de elementos en pasos sucesivos de Shellsort con espacios 5, 3, 1

Shellsort , también conocido como clasificación de Shell o método de Shell , es una clasificación de comparación in situ . Se puede ver ya sea como una generalización de la clasificación por intercambio ( burbuja especie ) o clasificación por inserción ( tipo inserción ). ^[3] El método comienza clasificando pares de elementos muy separados entre sí, luego reduciendo progresivamente la brecha entre los elementos que se van a comparar. Al comenzar con elementos muy separados, puede mover algunos elementos fuera de lugar a su posición más rápido que un simple intercambio vecino más cercano. Donald Shell publicó la primera versión de este tipo en 1959. ^{[4] [5]}El tiempo de ejecución de Shellsort depende en gran medida de la secuencia de espacios que utiliza. Para muchas variantes prácticas, determinar su complejidad temporal sigue siendo un problema abierto .

Descripción

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 se produzca una lista ordenada. Dicha lista se dice que es h -sorted. También se puede considerar como h listas intercaladas, cada una clasificada individualmente. ^[6] Comenzar con valores grandes de h permite que los elementos se muevan largas distancias en la lista original, reduciendo rápidamente grandes cantidades de desorden y dejando menos trabajo para los pasos de h -sort más pequeños . ^[7] Si la lista está ordenada por k para un entero menor k, entonces la lista permanece ordenada por h . Siguiendo esta idea para una secuencia decreciente de valores h que terminan en 1, se garantiza que dejará una lista ordenada al final. ^[6]

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, 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 es siempre 1 para finalizar la clasificación (terminando efectivamente con una clasificación de inserción ordinaria).

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

	un 1	un 2	un 3	a 4	un 5	un 6	un 7	un 8	un 9	un 10	a 11	a 12
Los datos de entrada	62	83	18	53	07	17	95	86	47	69	25	28
Después de clasificar 5	17	28	18	47	07	25	83	86	53	69	62	95
Después de 3-clasificación	17	07	18	47	28	25	69	62	53	83	86	95
Después de 1 clasificación	07	17	18	25	28	47	53	62	69	83	86	95

La primera pasada, clasificación 5, realiza la clasificación por inserción en cinco subarreglos separados ( a ₁ , a ₆ , a ₁₁ ), ( a ₂ , a ₇ , a ₁₂ ), ( a ₃ , a ₈ ), ( a ₄ , a ₉ ), ( un ₅ , un ₁₀ ). Por ejemplo, cambia el subarreglo ( un ₁ , un ₆ , un ₁₁) de (62, 17, 25) a (17, 25, 62). La siguiente pasada, 3-sorting, realiza una ordenación por inserción en los tres subarreglos ( a ₁ , a ₄ , a ₇ , a ₁₀ ), ( a ₂ , a ₅ , a ₈ , a ₁₁ ), ( a ₃ , a ₆ , un ₉ , un ₁₂ ). El último paso, 1-sorting, es un tipo de inserción ordinario de toda la matriz ( a ₁ , ..., a ₁₂ ).

Como ilustra el ejemplo, los subarreglos en los que opera Shellsort son inicialmente cortos; después son más largos pero casi ordenados. En ambos casos, la clasificación por inserción funciona de manera eficiente.

Shellsort no es estable : puede cambiar el orden relativo de elementos con valores iguales. Es un algoritmo de clasificación adaptativo en el sentido de que se ejecuta más rápido cuando la entrada está parcialmente clasificada.

Pseudocódigo

Utilizando la secuencia de huecos de Marcin Ciura, con una ordenación de inserción interna.

# Ordene una matriz a [0 ... n-1]. huecos  =  [ 701 ,  301 ,  132 ,  57 ,  23 ,  10 ,  4 ,  1 ]# Comience con la mayor brecha y el trabajo a una distancia de 1 foreach  ( brecha  en  las lagunas ) {  # Hacer una inserción con huecos de clasificación para este tamaño de la separación.  # Los primeros elementos de espacio a [0..gap-1] ya están en orden de  espacio # sigue agregando un elemento más hasta que toda la matriz esté ordenada  por  espacios ( i  =  espacio ;  i  <  n ;  i  + =  1 )  {  # agregar a [i] a los elementos que han sido ordenados por espacios  # guardar un [i] en temp y hacer un agujero en la posición i  temp  =  a [ i ] # desplazar elementos anteriores ordenados por espacios hacia arriba hasta que se encuentre la ubicación correcta para un [i]  para  ( j  =  i ;  j  > =  espacio  y  a [ j  -  espacio ]  >  temp ;  j  - =  espacio )  {  a [ j ]  =  a [ j  -  gap ]  }  # poner temp (el original a [i]) en su ubicación correcta  a [ j ]  =  temp  } }

Secuencias de huecos

La cuestión de decidir qué secuencia de huecos utilizar es difícil. Cada secuencia de espacios que contiene 1 produce una clasificación correcta (ya que esto hace que la pasada final sea una clasificación de inserción ordinaria); sin embargo, las propiedades de las versiones de Shellsort así obtenidas pueden ser muy diferentes. Muy pocos huecos ralentizan los pases y demasiados huecos producen una sobrecarga.

La siguiente tabla compara la mayoría de las secuencias de huecos propuestas publicadas hasta ahora. Algunos de ellos tienen elementos decrecientes que dependen del tamaño de la matriz ordenada ( N ). Otros son sucesiones infinitas crecientes, cuyos elementos menores que N deben usarse en orden inverso.

OEIS	Término general ( k ≥ 1)	Huecos de hormigón	Complejidad temporal en el peor de los casos	Autor y año de publicación
	${\displaystyle \left\lfloor {\frac {N}{2^{k}}}\right\rfloor }$	${\displaystyle \left\lfloor {\frac {N}{2}}\right\rfloor ,\left\lfloor {\frac {N}{4}}\right\rfloor ,\ldots ,1}$	${\displaystyle \Theta \left(N^{2}\right)}$[por ejemplo, cuando N = 2 p ]	Shell , 1959 [4]
	${\displaystyle 2\left\lfloor {\frac {N}{2^{k+1}}}\right\rfloor +1}$	${\displaystyle 2\left\lfloor {\frac {N}{4}}\right\rfloor +1,\ldots ,3,1}$	${\displaystyle \Theta \left(N^{\frac {3}{2}}\right)}$	Frank y Lazarus, 1960 [8]
A000225	${\displaystyle 2^{k}-1}$	${\displaystyle 1,3,7,15,31,63,\ldots }$	${\displaystyle \Theta \left(N^{\frac {3}{2}}\right)}$	Hibbard , 1963 [9]
A083318	${\displaystyle 2^{k}+1}$, con el prefijo 1	${\displaystyle 1,3,5,9,17,33,65,\ldots }$	${\displaystyle \Theta \left(N^{\frac {3}{2}}\right)}$	Papernov y Stasevich, 1965 [10]
A003586	Números sucesivos del formulario ${\displaystyle 2^{p}3^{q}}$( 3 números suaves )	${\displaystyle 1,2,3,4,6,8,9,12,\ldots }$	${\displaystyle \Theta \left(N\log ^{2}N\right)}$	Pratt , 1971 [1]
A003462	${\displaystyle {\frac {3^{k}-1}{2}}}$, no mayor que ${\displaystyle \left\lceil {\frac {N}{3}}\right\rceil }$	${\displaystyle 1,4,13,40,121,\ldots }$	${\displaystyle \Theta \left(N^{\frac {3}{2}}\right)}$	Knuth , 1973, [3] basado en Pratt , 1971 [1]
A036569	${\displaystyle {\begin{aligned}&\prod \limits _{I}a_{q},{\hbox{where}}\\a_{0}={}&3\\a_{q}={}&\min \left\{n\in \mathbb {N} \colon n\geq \left({\frac {5}{2}}\right)^{q+1},\forall p\colon 0\leq p<q\Rightarrow \gcd(a_{p},n)=1\right\}\\I={}&\left\{0\leq q<r\mid q\neq {\frac {1}{2}}\left(r^{2}+r\right)-k\right\}\\r={}&\left\lfloor {\sqrt {2k+{\sqrt {2k}}}}\right\rfloor \end{aligned}}}$	${\displaystyle 1,3,7,21,48,112,\ldots }$	${\displaystyle O\left(N^{1+{\sqrt {\frac {8\ln \left(5/2\right)}{\ln(N)}}}}\right)}$	Incerpi y Sedgewick , 1985, [11] Knuth [3]
A036562	${\displaystyle 4^{k}+3\cdot 2^{k-1}+1}$, con el prefijo 1	${\displaystyle 1,8,23,77,281,\ldots }$	${\displaystyle O\left(N^{\frac {4}{3}}\right)}$	Sedgewick, 1982 [6]
A033622	${\displaystyle {\begin{cases}9\left(2^{k}-2^{\frac {k}{2}}\right)+1&k{\text{ even}},\\8\cdot 2^{k}-6\cdot 2^{(k+1)/2}+1&k{\text{ odd}}\end{cases}}}$	${\displaystyle 1,5,19,41,109,\ldots }$	${\displaystyle O\left(N^{\frac {4}{3}}\right)}$	Sedgewick, 1986 [12]
	${\displaystyle h_{k}=\max \left\{\left\lfloor {\frac {5h_{k-1}-1}{11}}\right\rfloor ,1\right\},h_{0}=N}$	${\displaystyle \left\lfloor {\frac {5N-1}{11}}\right\rfloor ,\left\lfloor {\frac {5}{11}}\left\lfloor {\frac {5N-1}{11}}\right\rfloor -1\right\rfloor ,\ldots ,1}$	Desconocido	Gonnet y Baeza-Yates , 1991 [13]
A108870	${\displaystyle \left\lceil {\frac {1}{5}}\left(9\cdot \left({\frac {9}{4}}\right)^{k-1}-4\right)\right\rceil }$	${\displaystyle 1,4,9,20,46,103,\ldots }$	Desconocido	Tokuda, 1992 [14]
A102549	Desconocido (derivado experimentalmente)	${\displaystyle 1,4,10,23,57,132,301,701}$	Desconocido	Ciura, 2001 [15]

Cuando la representación binaria de N contiene muchos ceros consecutivos, Shellsort utilizando la secuencia de espacios original de Shell hace comparaciones Θ ( N ² ) en el peor de los casos. Por ejemplo, este caso ocurre 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 mayor complejidad que el O ( N  log  N ) que es óptimo para tipos de comparación, la versión de Pratt se presta para clasificar redes y tiene la misma complejidad de puerta asintótica que el clasificador bitónico de Batcher .

Gonnet y Baeza-Yates observaron que Shellsort hace la menor cantidad de comparaciones en promedio cuando las proporciones de brechas sucesivas son aproximadamente iguales a 2.2. ^[13] Esta es la razón por la 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 utilizar espacios que tengan divisores comunes máximos bajos o que sean coprimos por pares . ^{[16] [ verificación fallida ]}

Con respecto al número promedio de comparaciones, la secuencia de Ciura ^[15] tiene el mejor desempeño conocido; los espacios de 701 no se determinaron, pero la secuencia se puede extender aún más de acuerdo con 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 }$, donde ${\displaystyle h'_{k}=2.25h'_{k-1}+1}$, ${\displaystyle h'_{1}=1}$, se puede recomendar para aplicaciones prácticas.

Si el tamaño máximo de entrada es pequeño, como puede ocurrir si de Shell se utiliza en pequeñas submatrices por otro recursivo algoritmo de clasificación tales como quicksort o de combinación de tipo , entonces es posible para tabular una secuencia óptima para cada tamaño de entrada. ^[17]

Complejidad computacional

Se cumple la siguiente propiedad: después de h ₂ -ordenar cualquier matriz h ₁ -sorted, la matriz permanece h ₁ -sorted. ^[18] Cada matriz h ₁ clasificada y h ₂ también está clasificada ( a ₁ h ₁ + a ₂ h ₂ ), para cualquier número entero no negativo a ₁ y a ₂ . Por lo tanto, la complejidad del peor caso de Shellsort está relacionada con el problema de Frobenius : para enteros dados h ₁ , ..., h _ncon gcd = 1, el número de Frobenius g ( h ₁ , ..., h _n ) es el número entero más grande que no puede ser representado como una ₁ h ₁ + ... + a _n h _n con entero no negativo un ₁ , .. ., una _n . Usando fórmulas conocidas para números de Frobenius, podemos determinar la complejidad del peor caso de Shellsort para varias clases de secuencias de espacios. ^[19] Los resultados probados se muestran en la tabla anterior.

Con respecto al número promedio de operaciones, ninguno de los resultados probados se refiere a una secuencia práctica de brechas. Para espacios que son potencias de dos, Espelid calculó este promedio como${\displaystyle 0.5349N{\sqrt {N}}-0.4387N-0.097{\sqrt {N}}+O(1)}$. ^[20] Knuth determinó que la complejidad promedio de clasificar una matriz de N elementos con dos espacios ( h , 1)${\displaystyle {\frac {2N^{2}}{h}}+{\sqrt {\pi N^{3}h}}}$. ^[3] Se deduce que un Shellsort de dos pasadas con h = Θ ( N ^1/3 ) hace en promedio O ( N ^5/3 ) comparaciones / inversiones / tiempo de ejecución. Yao encontró la complejidad promedio de un Shellsort de tres pasadas. ^[21] Su resultado fue refinado por Janson y Knuth: ^[22] el número promedio de comparaciones / inversiones / tiempo de ejecución realizado durante un Shellsort con tres espacios ( ch , cg , 1), donde h y g son coprimos, es${\displaystyle {\frac {N^{2}}{4ch}}+O(N)}$ en la primera pasada, ${\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 pase. ψ ( 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 medio 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) el elemento se mueve. ^{[13] Las} aproximaciones del número medio de operaciones presentadas anteriormente para otras secuencias fallan cuando las matrices ordenadas contienen millones de elementos.

El siguiente gráfico muestra el número medio de comparaciones de elementos en varias variantes de Shellsort, dividido por el límite inferior teórico, es decir, log ₂ N !, donde se ha ampliado la secuencia 1, 4, 10, 23, 57, 132, 301, 701 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 ^[23] demostraron el siguiente límite inferior para el orden del número promedio de operaciones / tiempo de ejecución en un Shellsort p -pass: Ω ( 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 Nsolo cuando se utilizan secuencias de espacios cuyo número de espacios 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 casos promedio, que es óptimo para tipos de comparación. Vitányi ^[24] mejoró el límite inferior para cada número de pases.${\displaystyle p}$ para ${\displaystyle \Omega (N\sum _{k=1}^{p}h_{k-1}/h_{k})}$donde ${\displaystyle h_{0}=N}$. Este resultado implica, por ejemplo, el límite 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 (inferior y superior) conocidos actualmente para el caso medio se corresponden con precisión 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 muestra 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 incremento para cuatro pasadas que tiene 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 del 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ápido como${\displaystyle \Omega \left(N\left({\log N \over \log \log N}\right)^{2}\right)}$. ^{[25] [26]}

Aplicaciones

Shellsort realiza más operaciones y tiene una mayor tasa de fallas de caché que Quicksort . Sin embargo, dado que se puede implementar usando poco código y no usa la pila de llamadas , algunas implementaciones de la función qsort en la biblioteca estándar de C dirigidas a sistemas embebidos la usan en lugar de quicksort. Shellsort se usa, por ejemplo, en la biblioteca uClibc . ^[27] Por razones similares, en el pasado, Shellsort se usaba en el kernel de Linux . ^[28]

Shellsort también puede servir como un sub-algoritmo de ordenamiento introspectivo , para ordenar subarreglos cortos y prevenir una desaceleración cuando la profundidad de recursividad excede un límite dado. Este principio se emplea, por ejemplo, en el compresor bzip2 . ^[29]

Ver también

• Tipo de peine

Referencias

1. Pratt, Vaughan Ronald (1979). Shellsort y Sorting Networks (Disertaciones destacadas en Ciencias de la Computación) . Guirnalda. ISBN 978-0-8240-4406-0.
2. "Shellsort y comparaciones" .
3. Knuth, Donald E. (1997). "Método de Shell". El arte de la programación informática. Volumen 3: Clasificación y búsqueda (2ª ed.). Reading, Massachusetts: Addison-Wesley. págs. 83–95. ISBN 978-0-201-89685-5.
4. Shell, DL (1959). "Un procedimiento de clasificación de alta velocidad" (PDF) . Comunicaciones de la ACM . 2 (7): 30–32. doi : 10.1145 / 368370.368387 .
5. Algunos libros de texto y referencias más antiguos llaman a esto el tipo "Shell-Metzner" en honor a Marlene Metzner Norton , pero según Metzner, "no tuve nada que ver con el tipo, y mi nombre nunca debería haber estado asociado". Consulte "Clasificación de Shell" . Instituto Nacional de Estándares y Tecnología . Consultado el 17 de julio de 2007 .
6. Sedgewick, Robert (1998). Algoritmos en C . 1 (3ª ed.). Addison-Wesley. págs.  273-281 . ISBN 978-0-201-31452-6.
7. Kernighan, Brian W .; Ritchie, Dennis M. (1996). El lenguaje de programación C (2ª ed.). Prentice Hall. pag. 62. ISBN 978-7-302-02412-5.
8. Frank, RM; Lázaro, RB (1960). "Un procedimiento de clasificación de alta velocidad". Comunicaciones de la ACM . 3 (1): 20-22. doi : 10.1145 / 366947.366957 .
9. Hibbard, Thomas N. (1963). "Un estudio empírico de clasificación de almacenamiento mínimo". Comunicaciones de la ACM . 6 (5): 206–213. doi : 10.1145 / 366552.366557 .
10. Papernov, AA; Stasevich, GV (1965). "Un método de clasificación de información en memorias de computadora" (PDF) . Problemas de transmisión de información . 1 (3): 63–75.
11. Incerpi, Janet; Sedgewick, Robert (1985). "Límites superiores mejorados en Shellsort" (PDF) . Revista de Ciencias de la Computación y Sistemas . 31 (2): 210–224. doi : 10.1016 / 0022-0000 (85) 90042-x .
12. Sedgewick, Robert (1986). "Un nuevo límite superior para Shellsort". Revista de algoritmos . 7 (2): 159-173. doi : 10.1016 / 0196-6774 (86) 90001-5 .
13. Gonnet, Gaston H .; Baeza-Yates, Ricardo (1991). "Shellsort". Manual de algoritmos y estructuras de datos: en Pascal y C (2ª ed.). Reading, Massachusetts: Addison-Wesley. págs. 161-163. ISBN 978-0-201-41607-7. Experimentos extensos indican que la secuencia definida por α = 0,45454 <5/11 funciona significativamente mejor que otras secuencias. La forma más fácil de calcular ⌊ 0.45454 n ⌋ es utilizando aritmética de números enteros.(5 * n — 1)/11
14. Tokuda, Naoyuki (1992). "Un Shellsort mejorado". En van Leeuven, Jan (ed.). Actas del 12º Congreso Mundial de Computación de IFIP sobre algoritmos, software y arquitectura . Amsterdam: North-Holland Publishing Co. págs. 449–457. ISBN 978-0-444-89747-3.
15. Ciura, Marcin (2001). "Mejores incrementos para el caso medio de Shellsort" (PDF) . En Freiwalds, Rusins ​​(ed.). Actas del XIII Simposio Internacional sobre Fundamentos de la Teoría de la Computación . Londres: Springer-Verlag. págs. 106-117. ISBN  978-3-540-42487-1.
16. Sedgewick, Robert (1998). "Shellsort". Algoritmos en C ++, Partes 1–4: Fundamentos, Estructura de datos, Clasificación, Búsqueda . Reading, Massachusetts: Addison-Wesley. págs. 285-292. ISBN 978-0-201-35088-3.
17. Forshell, Olof (22 de mayo de 2018). "¿Cómo elegir las longitudes de mis subsecuencias para un tipo de caparazón?" . Desbordamiento de pila . ¿Comentarios adicionales en la secuencia de huecos más rápida para la clasificación de proyectiles? (23 de mayo de 2018).
18. Gale, David ; Karp, Richard M. (abril de 1972). "Un fenómeno en la teoría de la clasificación" (PDF) . Revista de Ciencias de la Computación y Sistemas . 6 (2): 103-115. doi : 10.1016 / S0022-0000 (72) 80016-3 .
19. Selmer, Ernst S. (marzo de 1989). "Sobre Shellsort y el problema de Frobenius" (PDF) . BIT Matemáticas numéricas . 29 (1): 37–40. doi : 10.1007 / BF01932703 . hdl : 1956/19572 .
20. Espelid, Terje O. (diciembre de 1973). "Análisis de un algoritmo Shellsort". BIT Matemáticas numéricas . 13 (4): 394–400. doi : 10.1007 / BF01933401 . El resultado citado es la ecuación (8) de la p. 399.
21. Yao, Andrew Chi-Chih (1980). "Un análisis de ( h , k , 1) -Shellsort" (PDF) . Revista de algoritmos . 1 (1): 14–50. doi : 10.1016 / 0196-6774 (80) 90003-6 . STAN-CS-79-726. Archivado desde el original (PDF) el 4 de marzo de 2019.
22. Janson, Svante ; Knuth, Donald E. (1997). "Shellsort con tres incrementos" (PDF) . Estructuras y algoritmos aleatorios . 10 (1-2): 125-142. arXiv : cs / 9608105 . CiteSeerX 10.1.1.54.9911 . doi : 10.1002 / (SICI) 1098-2418 (199701/03) 10: 1/2 <125 :: AID-RSA6> 3.0.CO; 2-X .  
23. Jiang, Tao; Li, Ming ; Vitányi, Paul (septiembre de 2000). "Un límite inferior en la complejidad de casos promedio de Shellsort" (PDF) . Revista de la ACM . 47 (5): 905–911. arXiv : cs / 9906008 . CiteSeerX 10.1.1.6.6508 . doi : 10.1145 / 355483.355488 .  
24. Vitányi, Paul (marzo de 2018). "En la complejidad de casos promedio de Shellsort" (PDF) . Estructuras y algoritmos aleatorios . 52 (2): 354–363. arXiv : 1501.06461 . doi : 10.1002 / rsa.20737 .
25. Plaxton, C. Greg; Poonen, Bjorn ; Suel, Torsten (24 a 27 de octubre de 1992). Límites inferiores mejorados para Shellsort (PDF) . Simposio anual sobre fundamentos de la informática (FOCS 1992) . 33 . Pittsburgh, Estados Unidos. págs. 226-235. CiteSeerX 10.1.1.43.1393 . doi : 10.1109 / SFCS.1992.267769 . ISBN   978-0-8186-2900-6.
26. Plaxton, C. Greg; Suel, Torsten (mayo de 1997). "Límites inferiores para Shellsort" (PDF) . Revista de algoritmos . 23 (2): 221–240. CiteSeerX 10.1.1.460.2429 . doi : 10.1006 / jagm.1996.0825 .  
27. Novoa, Manuel III. "libc / stdlib / stdlib.c" . Consultado el 29 de octubre de 2014 .
28. "núcleo / grupos.c" . Consultado el 5 de mayo de 2012 .
29. Julian Seward. "bzip2 / blocksort.c" . Consultado el 30 de marzo de 2011 .

Bibliografía

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

Enlaces externos

• Algoritmos de clasificación animados: clasificación de Shell en la Wayback Machine (archivado el 10 de marzo de 2015) - demostración gráfica
• Shellsort con espacios 5, 3, 1 como danza folclórica húngara