Ordenar por conchas

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

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

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 .

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. 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 se} ordena la lista con 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 ₁ , 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). El siguiente paso, 3-sorting, realiza un ordenamiento por inserción en las tres submatrices ( a ₁ , a ₄ , a ₇ , a ₁₀ ), ( a ₂ , a ₅ , a ₈ , a ₁₁ ), ( a ₃ , a ₆ , a ₉ , a ₁₂ ). El último paso, 1-sorting, es una ordenación por inserción ordinaria de toda la matriz ( un ₁ ,..., un ₁₂ ).

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.

Pseudocódigo

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 todos los elementos 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 } }                                                 

Secuencias de brecha

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 ² ) 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 . ${\displaystyle h_{k}=\lfloor 2.25h_{k-1}\rfloor }$

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

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]}

Complejidad computacional

La siguiente propiedad se cumple: después de la h ₂ -ordenación de cualquier matriz h _{1 -ordenada, la matriz permanece} h ₁ -ordenada. ^[21] Toda matriz h ₁ -ordenada y h ₂ -ordenada también está ( a ₁ h ₁ + a ₂ h ₂ )-ordenada, para cualesquiera enteros no negativos a ₁ y a ₂ . Por lo tanto, la complejidad del peor caso de Shellsort está relacionada con el problema de Frobenius : para los enteros dados h ₁ ,..., h _n con mcd = 1, el número de Frobenius g ( h ₁ ,..., h _n ) es el mayor entero que no se puede representar como a ₁ h ₁ + ... + a _n h _n con el 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 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 ). ${\displaystyle 0.5349N{\sqrt {N}}-0.4387N-0.097{\sqrt {N}}+O(1)}$ ${\displaystyle {\frac {2N^{2}}{h}}+{\sqrt {\pi N^{3}h}}}$ ${\displaystyle {\frac {N^{2}}{4ch}}+O(N)}$ ${\displaystyle {\frac {1}{8g}}{\sqrt {\frac {\pi }{ch}}}(h-1)N^{3/2}+O(hN)}$ ${\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)}$ ${\displaystyle {\sqrt {\frac {\pi h}{128}}}g+O\left(g^{-1/2}h^{1/2}\right)+O\left(gh^{-1/2}\right)}$

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 ₂ N !. La secuencia de Ciuria 1, 4, 10, 23, 57, 132, 301, 701 (etiquetada Ci01) se ha extendido de acuerdo con 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 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 ₂ 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 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 (inferior y superior) 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 muestra 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 ${\displaystyle p}$ ${\displaystyle \Omega (N\sum _{k=1}^{p}h_{k-1}/h_{k})}$ ${\displaystyle h_{0}=N}$ ${\displaystyle p}$ ${\displaystyle \Theta (N^{23/15})}$ ${\displaystyle \Omega (pn^{1+1/p})=\Omega (n^{5/4})}$ ${\displaystyle h_{1}=n^{11/16},}$ ${\displaystyle h_{2}=n^{7/16},}$ ${\displaystyle h_{3}=n^{3/16},}$ ${\displaystyle h_{4}=1}$ ${\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 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] ${\displaystyle \Omega \left(N\left({\log N \over \log \log N}\right)^{2}\right)}$ ${\displaystyle \Omega \left(N{{(\log N)^{2}} \over {\log \log N}}\right)}$ ${\displaystyle h_{s+1}>h_{s}}$ ${\displaystyle s}$

Aplicaciones

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]

Véase también

• Clasificación por peine

Referencias

1. Pratt, Vaughan Ronald (1979). Shellsort y redes de ordenación (tesis doctorales destacadas en ciencias de la computación) (PDF) . Garland. ISBN 978-0-8240-4406-0Archivado (PDF) del original el 7 de septiembre de 2021.
2. "Shellsort & Comparisons". Archivado desde el original el 20 de diciembre de 2019. Consultado el 14 de noviembre de 2015 .
3. 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. págs. 83–95. ISBN 978-0-201-89685-5.
4. Shell, DL (1959). "A High-Speed ​​Sorting Procedure" (PDF) . Comunicaciones de la ACM . 2 (7): 30–32. doi :10.1145/368370.368387. S2CID  28572656. Archivado desde el original (PDF) el 30 de agosto de 2017 . Consultado el 18 de octubre de 2011 .
5. Algunos libros de texto y referencias más antiguos denominan a esta clasificación "Shell-Metzner" en honor a Marlene Metzner Norton, pero según Metzner, "no tuve nada que ver con esta clasificación y mi nombre nunca debió haber estado asociado a ella". Véase "Sorteo Shell". Instituto Nacional de Estándares y Tecnología . Consultado el 17 de julio de 2007 .
6. Sedgewick, Robert (1998). Algoritmos en C. Vol. 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. pág. 62. ISBN  978-7-302-02412-5.
8. Frank, RM; Lazarus, RB (1960). "Un procedimiento de clasificación de alta velocidad". Comunicaciones de la ACM . 3 (1): 20–22. doi : 10.1145/366947.366957 . S2CID  34066017.
9. Hibbard, Thomas N. (1963). "Un estudio empírico de la clasificación de almacenamiento mínimo". Comunicaciones de la ACM . 6 (5): 206–213. doi : 10.1145/366552.366557 . S2CID  12146844.
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 de Sistemas . 31 (2): 210–224. doi :10.1016/0022-0000(85)90042-x.
12. Sedgewick, Robert (1986). "Un nuevo límite superior para Shellsort". Journal of Algorithms . 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-7Experimentos exhaustivos indican que la secuencia definida por α = 0,45454 < 5/11 tiene 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
14. Tokuda, Naoyuki (1992). "An Improved Shellsort". En van Leeuven, Jan (ed.). Actas del 12.º Congreso Mundial de Informática sobre Algoritmos, Software y Arquitectura de la IFIP . Ámsterdam: North-Holland Publishing Co., págs. 449-457. ISBN 978-0-444-89747-3.
15. Ciura, Marcin (2001). "Mejores incrementos para el caso promedio de Shellsort" (PDF) . En Freiwalds, Rusins ​​(ed.). Actas del 13.º Simposio internacional sobre fundamentos de la teoría de la computación . Londres: Springer-Verlag. pp. 106–117. ISBN. 978-3-540-42487-1Archivado desde el original (PDF) el 23 de septiembre de 2018.
16. Lee, Ying Wai (21 de diciembre de 2021). "Secuencia de brecha de Tokuda mejorada empíricamente en Shellsort". arXiv : 2112.11112 [cs.DS].
17. Skean, Oscar; Ehrenborg, Richard; Jaromczyk, Jerzy W. (1 de enero de 2023). "Perspectivas de optimización en Shellsort". arXiv : 2301.00316 [cs.DS].
18. Sedgewick, Robert (1998). "Shellsort". Algoritmos en C++, partes 1 a 4: fundamentos, estructura de datos, ordenación, búsqueda . Reading, Massachusetts: Addison-Wesley. págs. 285-292. ISBN 978-0-201-35088-3.
19. Forshell, Olof (22 de mayo de 2018). "¿Cómo elegir las longitudes de mis subsecuencias para una ordenación de shell?". Desbordamiento de pila . Comentario adicional en ¿La secuencia de espacios más rápida para la clasificación de conchas? (23 de mayo de 2018).
20. Lee, Ying Wai (21 de diciembre de 2021). "Secuencias de brecha óptimas en Shellsort para n ≤ 16 elementos". arXiv : 2112.11127 [math.CO].
21. 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 de Sistemas . 6 (2): 103–115. doi : 10.1016/S0022-0000(72)80016-3 .
22. Selmer, Ernst S. (marzo de 1989). "Sobre Shellsort y el problema de Frobenius" (PDF) . BIT Numerical Mathematics . 29 (1): 37–40. doi :10.1007/BF01932703. hdl : 1956/19572 . S2CID  : 32467267.
23. Weiss, Mark Allen (1989). "Un buen argumento a favor de Shellsort". Congressus Numerantium . 73 : 59–62.
24. Espelid, Terje O. (diciembre de 1973). "Análisis de un algoritmo Shellsort". BIT Numerical Mathematics . 13 (4): 394–400. doi :10.1007/BF01933401. S2CID  119443598. El resultado citado es la ecuación (8) en la página 399.
25. Yao, Andrew Chi-Chih (1980). "An Analysis of (h, k, 1)-Shellsort" (PDF) . Journal of Algorithms . 1 (1): 14–50. doi :10.1016/0196-6774(80)90003-6. S2CID  3054966. STAN-CS-79-726. Archivado desde el original (PDF) el 4 de marzo de 2019.
26. Janson, Svante ; Knuth, Donald E. (1997). "Shellsort con tres incrementos" (PDF) . Estructuras aleatorias y algoritmos . 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. 
27. Jiang, Tao; Li, Ming ; Vitányi, Paul (septiembre de 2000). "Un límite inferior en la complejidad del caso 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. S2CID  3265123. 
28. Vitányi, Paul (marzo de 2018). "Sobre la complejidad del caso promedio de Shellsort" (PDF) . Random Structures and Algorithms . 52 (2): 354–363. arXiv : 1501.06461 . doi :10.1002/rsa.20737. S2CID  6833808.
29. Plaxton, C. Greg; Poonen, Bjorn ; Suel, Torsten (24–27 de octubre de 1992). "Improved lower bounds for Shellsort" (PDF) . Actas del 33.° Simposio anual sobre fundamentos de la informática . Vol. 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.S2CID15095863  .​{{cite book}}: CS1 maint: location missing publisher (link)
30. Plaxton, C. Greg; Suel, Torsten (mayo de 1997). "Límites inferiores para Shellsort" (PDF) . Journal of Algorithms . 23 (2): 221–240. CiteSeerX 10.1.1.460.2429 . doi :10.1006/jagm.1996.0825. 
31. Cypher, Robert (1993). "Un límite inferior en el tamaño de las redes de ordenamiento Shellsort". Revista SIAM de Computación . 22 : 62–71. doi :10.1137/0222006.
32. Novoa, Manuel III. «libc/stdlib/stdlib.c» . Consultado el 29 de octubre de 2014 .
33. "kernel/groups.c". GitHub . Consultado el 5 de mayo de 2012 .
34. Julian Seward. "bzip2/blocksort.c" . Consultado el 30 de marzo de 2011 .

Bibliografía

• 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 de Shellsort y algoritmos relacionados, Robert Sedgewick, Cuarto Simposio Europeo sobre Algoritmos, Barcelona, ​​septiembre de 1996.

Enlaces externos

• Algoritmos de ordenamiento animados: Shell Sort en Wayback Machine (archivado el 10 de marzo de 2015): demostración gráfica
• Baile de conchas con los espacios 5, 3 y 1 como danza folclórica húngara